We prove the existence conjecture for combinatorial designs, answering a question of Steiner from 1853. More generally, we show that the natural divisibility conditions are sufficient for clique decompositions of simplicial complexes that satisfy a certain pseudorandomness condition. As a further generalisation, we obtain the same conclusion only assuming an extendability property and the existence of a robust fractional clique decomposition.
Even the existence of designs with @math and any non-trivial' @math was open before the breakthrough result of Teirlinck @cite_38 confirming this. An improved bound on @math and a probabilistic method (a local limit theorem for certain random walks in high dimensions) for constructing many other rigid combinatorial structures was recently given by Kuperberg, Lovett and Peled @cite_8 . Their result for designs is somewhat complementary to ours, in that they can allow the parameters @math and @math to grow with @math , whereas we require them to be (essentially) constant. They also obtain much more precise estimates than we do for the number of designs (within their range of parameters).
@cite_38 @cite_8
2136834513 2963863740 2139964991 2508919161
We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, @math -designs, and @math -wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. The proof of existence is probabilistic. We show that a randomly chosen such object has the required properties with positive yet tiny probability. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps. We study branching random walks in random environment on the d- dimensional square lattice, d 1. In this model, the environment has nite range dependence, and the population size cannot decrease. We prove limit theorems (laws of large numbers) for the set of lattice sites which are visited up to a large time as well as for the local size of the population. The limiting shape of this set is compact and convex, and the local size is given by a concave growth exponent. Also, we obtain the law of large numbers for the logarithm of the total number of particles in the process. 1. Introduction and results We start with an informal description of the model we study in this paper. Particles live in Z d and evolve in discrete time. At each time, every particle is substituted by (possibly more than one) ospring which are placed in neighboring sites, independently of the other particles. The rules of ospring generation depend only on the location of the particle. The collection of those rules (so-called the environment) is itself random, it is chosen randomly before starting the process, and then it is kept xed during all the subsequent evolution of the particle system. We consider a finite random walk on a weighted graph G; we show that the fraction of time spent in a set of vertices A converges to the stationary probability @math with error probability exponentially small in the length of the random walk and the square of the size of the deviation from @math . The exponential bound is in terms of the expansion of G and improves previous results of [D. Aldous, Probab. Engrg. Inform. Sci., 1 (1987), pp. 33--46], [L. Lovasz and M. Simonovits, Random Structures Algorithms , 4 (1993), pp. 359--412], [M. Ajtai, J. Komlos, and E. Szemeredi, Deterministic simulation of logspace, in Proc. 19th ACM Symp. on Theory of Computing, 1987]. We show that taking the sample average from one trajectory gives a more efficient estimate of @math than the standard method of generating independent sample points from several trajectories. Using this more efficient sampling method, we improve the algorithms of Jerrum and Sinclair for approximating the number of perfect matchings in a dense graph and for approximating the partition function of a ferromagnetic Ising system, and we give an efficient algorithm to estimate the entropy of a random walk on an unweighted graph. [See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the @math -Approximate Near Neighbor Search problem. For the @math -dimensional Euclidean space and @math -point datasets, we develop a data structure with space @math and query time @math for every @math such that: This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor @math , improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for @math , improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.