Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

Converses For Secret Key Agreement and Secure Computing

We consider information theoretic secret key (SK) agreement and secure function computation by multiple parties observing correlated data, with access to an interactive public communication channel. Our main result is an upper bound on the SK length, which is derived using a reduction of binary hypothesis testing to multiparty SK agreement. Building on this basic result, we derive new converses for multiparty SK agreement. Furthermore, we derive converse results for the oblivious transfer problem and the bit commitment problem by relating them to SK agreement. Finally, we derive a necessary condition for the feasibility of secure computation by trusted parties that seek to compute a function of their collective data, using an interactive public communication that by itself does not give away the value of the function. In many cases, we strengthen and improve upon previously known converse bounds. Our results are single-shot and use only the given joint distribution of the correlated observations. For the case when the correlated observations consist of independent and identically distributed (in time) sequences, we derive strong versions of previously known converses.

Separation index of graphs and stacked 2-spheres

In 1987, Kalai proved that stacked spheres of dimension d >= 3 are characterised by the fact that they attain equality in Barnette's celebrated Lower Bound Theorem. This result does not extend to dimension d = 2. In this article, we give a characterisation of stacked 2-spheres using what we call the separation index. Namely, we show that the separation index of a triangulated 2-sphere is maximal if and only if it is stacked. In addition, we prove that, amongst all n-vertex triangulated 2-spheres, the separation index is minimised by some n-vertex flag sphere for n >= 6. Furthermore, we apply this characterisation of stacked 2-spheres to settle the outstanding 3-dimensional case of the Lutz-Sulanke-Swartz conjecture that ``tight-neighbourly triangulated manifolds are tight''. For dimension d >= 4, the conjecture has already been proved by Effenberger following a result of Novik and Swartz. (C) 2015 Elsevier Inc. All rights reserved.

Bearing capacity of circular footings over rock mass by using axisymmetric quasi lower bound finite element limit analysis

The ultimate bearing capacity of a circular footing, placed over rock mass, is evaluated by using the lower bound theorem of the limit analysis in conjunction with finite elements and nonlinear optimization. The generalized Hoek-Brown (HB) failure criterion, but by keeping a constant value of the exponent, alpha = 0.5, was used. The failure criterion was smoothened both in the meridian and pi planes. The nonlinear optimization was carried out by employing an interior point method based on the logarithmic barrier function. The results for the obtained bearing capacity were presented in a non-dimensional form for different values of GSI, m(i), sigma(ci)/(gamma b) and q/sigma(ci). Failure patterns were also examined for a few cases. For validating the results, computations were also performed for a strip footing as well. The results obtained from the analysis compare well with the data reported in literature. Since the equilibrium conditions are precisely satisfied only at the centroids of the elements, not everywhere in the domain, the obtained lower bound solution will be approximate not true. (C) 2015 Elsevier Ltd. All rights reserved.

Necessary and sufficient conditions for optimality in constrained general sum stochastic games

In this paper we first derive a necessary and sufficient condition for a stationary strategy to be the Nash equilibrium of discounted constrained stochastic game under certain assumptions. In this process we also develop a nonlinear (non-convex) optimization problem for a discounted constrained stochastic game. We use the linear best response functions of every player and complementary slackness theorem for linear programs to derive both the optimization problem and the equivalent condition. We then extend this result to average reward constrained stochastic games. Finally, we present a heuristic algorithm motivated by our necessary and sufficient conditions for a discounted cost constrained stochastic game. We numerically observe the convergence of this algorithm to Nash equilibrium. (C) 2015 Elsevier B.V. All rights reserved.

Near-Optimal Detection Thresholds for Bayesian Spectrum Sensing Under Fading

This paper considers the problem of energy-based, Bayesian spectrum sensing in cognitive radios under various fading environments. Under the well-known central limit theorem based model for energy detection, we derive analytically tractable expressions for near-optimal detection thresholds that minimize the probability of error under lognormal, Nakagami-m, and Weibull fading. For the Suzuki fading case, a generalized gamma approximation is provided, which saves on the computation of an integral. In each case, the accuracy of the theoretical expressions as compared to the optimal thresholds are illustrated through simulations.

A note on tetrablock contractions

A commuting triple of operators (A, B, P) on a Hilbert space H is called a tetrablock contraction if the closure of the set E = {(a(11),a(22),detA) : A = GRAPHICS] with parallel to A parallel to <1} is a spectral set. In this paper, we construct a functional model and produce a set of complete unitary invariants for a pure tetrablock contraction. In this construction, the fundamental operators, which are the unique solutions of the operator equations A - B* P = DPX1DP and B - A* P = DPX2DP where X-1, X-2 is an element of B(D-P) play a pivotal role. As a result of the functional model, we show that every pure tetrablock isometry (A, B, P) on an abstract Hilbert space H is unitarily equivalent to the tetrablock contraction (MG1*+G2z, MG2*+G1z, M-z) on H-DP*(2). (D), where G(1) and G(2) are the fundamental operators of (A*, B*, P*). We prove a Beurling Lax Halmos type theorem for a triple of operators (MF1*+F2z, MF2*+F1z, M-z), where epsilon is a Hilbert space and F-1, F-2 is an element of B(epsilon). We also deal with a natural example of tetrablock contraction on a functions space to find out its fundamental operators.

Deviated linear cyclic pursuit

This paper analyses deviated linear cyclic pursuit in which an agent pursues its leader with an angle of deviation in both the continuous- and discrete-time domains, while admitting heterogeneous gains and deviations for the agents. Sufficient conditions for the stability of such systems, in both the domains, are presented in this paper along with the derivation of the reachable set, which is a set of points where the agents may converge asymptotically. The stability conditions are derived based on Gershgorin's theorem. Simulations validating the theoretical results presented in this paper are provided.

Stabilization of Collective Motion in Synchronized, Balanced and Splay Phase Arrangements on a Desired Circle

This paper proposes a design methodology to stabilize collective circular motion of a group of N-identical agents moving at unit speed around individual circles of different radii and different centers. The collective circular motion studied in this paper is characterized by the clockwise rotation of all agents around a common circle of desired radius as well as center, which is fixed. Our interest is to achieve those collective circular motions in which the phases of the agents are arranged either in synchronized, in balanced or in splay formation. In synchronized formation, the agents and their centroid move in a common direction while in balanced formation, the movement of the agents ensures a fixed location of the centroid. The splay state is a special case of balanced formation, in which the phases are separated by multiples of 2 pi/N. We derive the feedback controls and prove the asymptotic stability of the desired collective circular motion by using Lyapunov theory and the LaSalle's Invariance principle.

Evaluation of the Effectiveness of Representative Methods for Determining Young's Modulus and Hardness from Instrumented Indentation Data

The effectiveness of Oliver & Pharr's (O&P's) method, Cheng & Cheng's (C&C's) method, and a new method developed by our group for estimating Young's modulus and hardness based on instrumented indentation was evaluated for the case of yield stress to reduced Young's modulus ratio (sigma(y)/E-r) >= 4.55 x 10(-4) and hardening coefficient (n) <= 0.45. Dimensional theorem and finite element simulations were applied to produce reference results for this purpose. Both O&P's and C&C's methods overestimated the Young's modulus under some conditions, whereas the error can be controlled within +/- 16% if the formulation was modified with appropriate correction functions. Similar modification was not introduced to our method for determining Young's modulus, while the maximum error of results was around +/- 13%. The errors of hardness values obtained from all the three methods could be even larger and were irreducible with any correction scheme. It is therefore suggested that when hardness values of different materials are concerned, relative comparison of the data obtained from a single standard measurement technique would be more practically useful. It is noted that the ranges of error derived from the analysis could be different if different ranges of material parameters sigma(y)/E-r and n are considered.

Chaotic dynamic analysis of viscoelastic plates

The dynamic buckling of viscoelastic plates with large deflection is investigated in this paper by using chaotic and fractal theory. The material behavior is given in terms of the Boltzmann superposition principle. in order to obtain accurate computation results, the nonlinear integro-differential dynamic equation is changed into an autonomic four-dimensional dynamical system. The numerical time integrations of equations are performed by using the fourth-order Runge-Kutta method. And the Lyapunov exponent spectrum, the fractal dimension of strange attractors and the time evolution of deflection are obtained. The influence of geometry nonlinearity and viscoelastic parameter on the dynamic buckling of viscoelastic plates is discussed.

Evaluación perceptivo auditiva de voces degradas y su correlación con medidas acústicas

Resumen: El objetivo es determinar utilizando las mediciones acústicas, qué información es más relevante para el oyente al momento de categorizar el grado general de disfonía. Se eligieron 8 (4 voces femeninas y 4 voces masculinas. Cada emisión fue evaluada auditivo perceptualmente a través del item G de la escala GRBAS por 10 oyentes experimentados y acústicamente mediante medidas de aperiodicidad, ruido y caos. El estudio estadístico de análisis discriminante señala la importancia de GNE, Jit y Jitter_cc y Lyapunov como parámetros predictores del grado general de disfonía. La aplicación del método k-means evidencia que existen rasgos en los parámetros acústicos empleados que permiten agrupar objetivamente las voces estudiadas con 100% de precisión para la clase 0, 96% a la clase 2 y 79% a la clase 3. Un mayor número y variabilidad de casos se necesita a fin de verificar los resultados preliminares.

Uniform stability of a particle approximation of the optimal filter derivative

Sequential Monte Carlo methods, also known as particle methods, are a widely used set of computational tools for inference in non-linear non-Gaussian state-space models. In many applications it may be necessary to compute the sensitivity, or derivative, of the optimal filter with respect to the static parameters of the state-space model; for instance, in order to obtain maximum likelihood model parameters of interest, or to compute the optimal controller in an optimal control problem. In Poyiadjis et al. [2011] an original particle algorithm to compute the filter derivative was proposed and it was shown using numerical examples that the particle estimate was numerically stable in the sense that it did not deteriorate over time. In this paper we substantiate this claim with a detailed theoretical study. Lp bounds and a central limit theorem for this particle approximation of the filter derivative are presented. It is further shown that under mixing conditions these Lp bounds and the asymptotic variance characterized by the central limit theorem are uniformly bounded with respect to the time index. We demon- strate the performance predicted by theory with several numerical examples. We also use the particle approximation of the filter derivative to perform online maximum likelihood parameter estimation for a stochastic volatility model.

Sequential decision making in general state space models

Many problems in control and signal processing can be formulated as sequential decision problems for general state space models. However, except for some simple models one cannot obtain analytical solutions and has to resort to approximation. In this thesis, we have investigated problems where Sequential Monte Carlo (SMC) methods can be combined with a gradient based search to provide solutions to online optimisation problems. We summarise the main contributions of the thesis as follows. Chapter 4 focuses on solving the sensor scheduling problem when cast as a controlled Hidden Markov Model. We consider the case in which the state, observation and action spaces are continuous. This general case is important as it is the natural framework for many applications. In sensor scheduling, our aim is to minimise the variance of the estimation error of the hidden state with respect to the action sequence. We present a novel SMC method that uses a stochastic gradient algorithm to find optimal actions. This is in contrast to existing works in the literature that only solve approximations to the original problem. In Chapter 5 we presented how an SMC can be used to solve a risk sensitive control problem. We adopt the use of the Feynman-Kac representation of a controlled Markov chain flow and exploit the properties of the logarithmic Lyapunov exponent, which lead to a policy gradient solution for the parameterised problem. The resulting SMC algorithm follows a similar structure with the Recursive Maximum Likelihood(RML) algorithm for online parameter estimation. In Chapters 6, 7 and 8, dynamic Graphical models were combined with with state space models for the purpose of online decentralised inference. We have concentrated more on the distributed parameter estimation problem using two Maximum Likelihood techniques, namely Recursive Maximum Likelihood (RML) and Expectation Maximization (EM). The resulting algorithms can be interpreted as an extension of the Belief Propagation (BP) algorithm to compute likelihood gradients. In order to design an SMC algorithm, in Chapter 8 uses a nonparametric approximations for Belief Propagation. The algorithms were successfully applied to solve the sensor localisation problem for sensor networks of small and medium size.

Hydrodynamic interaction between two vertical cylinders in water waves

The hydrodynamic interaction between two vertical cylinders in water waves is investigated based on the linearized potential flow theory. One of the two cylinders is fixed at the bottom while the other is articulated at the bottom and oscillates with small amplitudes in the direction of the incident wave. Both the diffracted wave and the radiation wave are studied in the present paper. A simple analytical expression for the velocity potential on the surface of each cylinder is obtained by means of Graf's addition theorem. The wave-excited forces and moments on the cylinders, the added masses and the radiation damping coefficients of the oscillating cylinder are all expressed explicitly in series form. The coefficients of the series are determined by solving algebraic equations. Several numerical examples are given to illustrate the effects of various parameters, such as the separation distance, the relative size of the cylinders, and the incident angle, on the first-order and steady second-order forces, the added masses and radiation-damping coefficients as well as the response of the oscillating cylinder.