The communication complexity of addition

Suppose each of k≤n ^o(1) players holds an n-bit number x _i in its hand. The players wish to determine if ∑ _i≤k x _i =s. We give a public-coin protocol with error 1% and communication O(k logk). The communication bound is independent of n, and for k≥3 improves on the O(k logn) bound by Nisan (Bolyai Soc. Math. Studies; 1993).     

Radar placement along banks of river

In this paper, we consider the Radar Placement and Power Assignment problem (RPPA) along a river. In this problem, a set of crucial points in the river are required to be monitored by a set of radars which are placed along the two banks. The goal is to choose the locations for the radars and assign powers to them such that all the crucial points are monitored and the total power is minimized. If each crucial point is required to be monitored by at least k radars, the problem is a k-Coverage RPPA problem (k-CRPPA). Under the assumption that the river is sufficiently smooth, one may focus on the RPPA problem along a strip (RPPAS). In this paper, we present an O(n ⁹) dynamic programming algorithm for the RPPAS, where n is the number of crucial points to be monitored. In the special case where radars are placed only along the upper bank, we present an O(kn ⁵) dynamic programming algorithm for the k-CRPPAS. For the special case that the power is linearly dependent on the radius, we present an O(n log n)-time \({2\sqrt 2}\)-approximation algorithm for the RPPAS.     

A cycle cover of a 2-edge-connected graph embedded with large face-width on an orientable surface

In 1985, Alon and Tarsi conjectured that the length of a shortest cycle cover of a bridgeless graph H is at most 7/5 |E(H|). The conjecture is still open. Let G be a 2-edge-connected graph embedded with face-width k on the non-spherical orientable surface S_g. We give an upper bound on the length of a cycle cover of G. In particular, if g = 1 and k ≥ 48, or g = 2 and k ≥ 427, or g ≥ 3 and k ≥ 288(4^g - 1), then the upper bound is 7/5 |E(G|), which means that Alon and Tarsi’s conjecture holds for such a graph.     

On increasing subsequences of minimal Erdös-Szekeres permutations

Let π be a minimal Erdös-Szekeres permutation of 1, 2, ..., n ², and let l _n,k be the length of the longest increasing subsequence in the segment (π(1), ..., π(k)). Under uniform measure we establish an exponentially decaying bound of the upper tail probability for l _n,k , and as a consequence we obtain a complete convergence, which is an improvement of Romik’s recent result. We also give a precise lower exponential tail for l _n,k .     

A new infeasible-interior-point algorithm for linear programming over symmetric cones

In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N(τ₁, τ₂, η), for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O(r^1.5logε^?1) for the Nesterov-Todd (NT) direction, and O(r²logε^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε > 0 is the required precision. If starting with a feasible point (x⁰, y⁰, s⁰) in N(τ₁, τ₂, η), the complexity bound is \(O\left( {\sqrt r \log {\varepsilon ^{ - 1}}} \right)\) for the NT direction, and O(rlogε^?1) for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.     

Upper bounds on the length of a shortest closed geodesic and quantitative Hurewicz theorem

In this paper we present two upper bounds on the length of a shortest closed geodesic on compact Riemannian manifolds. The first upper bound depends on an upper bound on sectional curvature and an upper bound on the volume of the manifold. The second upper bound will be given in terms of a lower bound on sectional curvature, an upper bound on the diameter and a lower bound on the volume.The related questions that will also be studied are the following: given a contractible k-dimensional sphere in M ⁿ , how “fast” can this sphere be contracted to a point, if π _i (M ⁿ )={0} for 1≤i<k. That is, what is the maximal length of the trajectory described by a point of a sphere under an “optimal” homotopy? Also, what is the “size” of the smallest non-contractible k-dimensional sphere in a (k-1)-connected manifold M ⁿ providing that M ⁿ is not k-connected?     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

Improved Approximation for Guarding Simple Galleries from the Perimeter

We provide an O(log?log?opt)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building ε-nets of size \(O(\frac{1}{\varepsilon}\log\log\frac{1}{\varepsilon})\) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Brönnimann and Goodrich to build an approximation algorithm from this ε-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon’s vertices. If a finite set of potential guard locations is not specified, e.g., when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm’s running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log?opt)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.     

<Emphasis Type="Italic">k</Emphasis>-means Requires Exponentially Many Iterations Even in the Plane

The k-means algorithm is a well-known method for partitioning n points that lie in the d-dimensional space into k clusters. Its main features are simplicity and speed in practice. Theoretically, however, the best known upper bound on its running time (i.e., n ^O(kd)) is, in general, exponential in the number of points (when kd=Ω(n/log?n)). Recently Arthur and Vassilvitskii (Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144–153, 2006) showed a super-polynomial worst-case analysis, improving the best known lower bound from Ω(n) to \(2^{\varOmega (\sqrt{n})}\) with a construction in \(d=\varOmega (\sqrt{n})\) dimensions. In Arthur and Vassilvitskii (Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144–153, 2006), they also conjectured the existence of super-polynomial lower bounds for any d≥2.Our contribution is twofold: we prove this conjecture and we improve the lower bound, by presenting a simple construction in the plane that leads to the exponential lower bound 2^Ω(n).     

Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control

We consider the numerical solution of the generalized Lyapunov and Stein equations in \(\mathbb {R}^{n}\), arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n³) computational complexity per iteration and an O(n²) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n⁶) complexity or the slower modified Newton’s methods of O(n³) complexity. The convergence and error analysis will be considered and numerical examples provided.     

In Metric-measure Spaces Sobolev Embedding is Equivalent to a Lower Bound for the Measure

We study Sobolev inequalities on doubling metric measure spaces. We investigate the relation between Sobolev embeddings and lower bound for measure. In particular, we prove that if the Sobolev inequality holds, then the measure μ satisfies the lower bound, i.e. there exists b such that μ(B(x,r))≥b r ^α for r∈(0,1] and any point x from metric space.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.     

On the sum of the L1 influences of bounded functions

Let f: {-1, 1}ⁿ → [-1, 1] have degree d as a multilinear polynomial. It is well-known that the total influence of f is at most d. Aaronson and Ambainis asked whether the total L₁ influence of f can also be bounded as a function of d. Ba?kurs and Bavarian answered this question in the affirmative, providing a bound of O(d³) for general functions and O(d²) for homogeneous functions. We improve on their results by providing a bound of d² for general functions and O(d log d) for homogeneous functions. In addition, we prove a bound of d/(2p) + o(d) for monotone functions, and provide a matching example.     

A Note on Average-Case Sorting

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman’s algorithm which is a variant of insertion sort and provide a basically tight upper bound: If μ is a distribution on permutations on n elements, then one may sort inputs from μ with expected number of comparisons that is at most H(μ) + 2n, where H is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation π, the algorithm sorts π by using at most \(\log _{2}(\frac {1}{\Pr _{\mu }(\pi )})+2n\) comparisons. A lower bound on the expected number of comparisons of H(μ) always holds, and a linear dependence on n is also required.     

On the Optimality of Gluing over Scales

We show that for every α>0, there exist n-point metric spaces (X,d) where every “scale” admits a Euclidean embedding with distortion at most α, but the whole space requires distortion at least \(\varOmega (\sqrt {\alpha\log n})\). This shows that the scale-gluing lemma (Lee in SODA’05: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 92–101, Society for Industrial and Applied Mathematics, Philadelphia, 2005) is tight and disproves a conjecture stated there. This matching upper bound was known to be tight at both endpoints, i.e., when α=Θ(1) and α=Θ(log?n), but nowhere in between.More specifically, we exhibit n-point spaces with doubling constant λ requiring Euclidean distortion \(\varOmega (\sqrt{\log\lambda\log n})\), which also shows that the technique of “measured descent” (Krauthgamer et al. in Geom. Funct. Anal. 15(4):839–858, 2005) is optimal. We extend this to L _p spaces with p>1, where one requires distortion at least Ω((log?n)^1/q (log?λ)^1?1/q ) when q=max?{p,2}, a result which is tight for every p>1.     

Finite time extinction of super-Brownian motions with deterministic catalyst

In this paper we consider a super-Brownian motion X with branching mechanism k(x)zα, where k(x) > 0 is a bounded Holder continuous function on Rd and infx∈Rd k(x) = 0. We prove that if k(x) ≥ //x// -l(0 ≤l < ∞) for sufficiently large x, then X has compact support property, and for dimension d = 1, if k(x) ≥exp(-l‖x‖)(0≤l < ∞) for sufficiently large x, then X also has compact support property. The maximal order of k(x) for finite time extinction is different between d = 1, d = 2 and d ≥ 3: it is O(‖x‖-(α+1)) in one dimension, O(‖x‖-2(log‖x‖)-(α+1) ) in two dimensions, and O(‖x‖2) in higher dimensions. These growth orders also turn out to be the maximum order for the nonexistence of a positive solution for 1/2Δu =k(x)uα.     

Khinchin’s inequality,Dunford-Pettis and compact operators on the space <Emphasis Type="Italic">C</Emphasis>([0, 1], <Emphasis Type="Italic">X</Emphasis>)

We prove that if X, Y are Banach spaces, Ω a compact Hausdorff space and U:C(Ω, X) → Y is a bounded linear operator, and if U is a Dunford-Pettis operator the range of the representing measure G(Σ) ? DP(X, Y) is an uniformly Dunford-Pettis family of operators and ∥G∥ is continuous at Ø. As applications of this result we give necessary and/or sufficient conditions that some bounded linear operators on the space C([0, 1], X) with values in c ₀ or l _p, (1 ≤ p < ∞) be Dunford-Pettis and/or compact operators, in which, Khinchin’s inequality plays an important role.     

Classification of Finite Coloured Linear Orderings

This paper concerns the classification of finite coloured linear orders up to n-equivalence. Ehrenfeucht–Fraïssé games are used to define what this means, and also to help analyze such structures. We give an explicit bound for the least number g(m,n) such that any finite m-coloured linear order is n-equivalent to some ordering of size ≤?g(m,n), from which it follows that g is computable. We give exact values for g(m,1) and g(m,2). The method of characters is developed and used.     

Embeddings of quotient division algebras of rings of differential operators

Let k be an algebraically closed field of characteristic zero, let X and Y be smooth irreducible algebraic curves over k, and let D(X) and D(Y) denote respectively the quotient division rings of the ring of differential operators of X and Y. We show that if there is a k-algebra embedding of D(X) into D(Y), then the genus of X must be less than or equal to the genus of Y, answering a question of the first-named author and Smoktunowicz.     

Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths

In 1982 Thomassen asked whether there exists an integer f(k,t) such that every strongly f(k,t)-connected tournament T admits a partition of its vertex set into t vertex classes V ₁,…V _t such that for all i the subtournament T[V _i] induced on T by V _i is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t)=O(k ⁷ t ⁴) suffices. As another application of our main result we give an affirmative answer to a question of Song as to whether, for any integer t, there exists aninteger h(t) such that every strongly h(t)-connected tournament has a 1-factor consisting of t vertex-disjoint cycles of prescribed lengths. We show that h(t)=O(t ⁵) suffices.