Let @math be a symmetric probability measure of finite entropy on a group @math . We show that if @math , then the pair @math has the Liouville property (all bounded @math -harmonic functions on @math are constant). Furthermore, if @math where @math , then the entropy of the @math -fold convolution power @math satisfies @math . This improves earlier results of Gournay and of Saloff-Coste and the second author. We extend the bounds to transitive graphs and illustrate their sharpness on a family of groups.
In the work of the second author with Saloff-Coste @cite_12 , an upper bound similar to Theorem was proved. More precisely, suppose @math is a symmetric probability measure of finite second moment on @math such that @math for some @math , then by [Theorem 1.7] Saloff-Coste2014 [ H_ (n) (n ^ 1+ n )^ 1- for any >0. ] In particular, this bound implies the Liouville property of @math for @math . Our results in this paper imply a sharper upper bound @math under the same assumption, and are applicable to a larger class of decay lower bounds.
@cite_12
2301298389
Adaptivity is an important feature of data analysis---the choice of questions to ask about a dataset often depends on previous interactions with the same dataset. However, statistical validity is typically studied in a nonadaptive model, where all questions are specified before the dataset is drawn. Recent work by (STOC, 2015) and Hardt and Ullman (FOCS, 2014) initiated the formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis. Specifically, suppose there is an unknown distribution @math and a set of @math independent samples @math is drawn from @math . We seek an algorithm that, given @math as input, accurately answers a sequence of adaptively chosen queries about the unknown distribution @math . How many samples @math must we draw from the distribution, as a function of the type of queries, the number of queries, and the desired level of accuracy? In this work we make two new contributions: (i) We give upper bounds on the number of samples @math that are needed to answer statistical queries. The bounds improve and simplify the work of (STOC, 2015), and have been applied in subsequent work by those authors (Science, 2015, NIPS, 2015). (ii) We prove the first upper bounds on the number of samples required to answer more general families of queries. These include arbitrary low-sensitivity queries and an important class of optimization queries. As in , our algorithms are based on a connection with algorithmic stability in the form of differential privacy. We extend their work by giving a quantitatively optimal, more general, and simpler proof of their main theorem that stability implies low generalization error. We also study weaker stability guarantees such as bounded KL divergence and total variation distance. Let @math be an i.i.d. sequence of random variables in @math , @math . We show that, for any function @math , under regularity conditions, [n^ 1 2 (n^ -1 i=1 ^n (X_i) f ^(X_i) - (x) ,dx ) P 0, ] where @math is the classical kernel estimator of the density of @math . This result is striking because it speeds up traditional rates, in root @math , derived from the central limit theorem when @math . Although this paper highlights some applications, we mainly address theoretical issues related to the later result. We derive upper bounds for the rate of convergence in probability. These bounds depend on the regularity of the functions @math and @math , the dimension @math and the bandwidth of the kernel estimator @math . Moreover, they are shown to be accurate since they are used as renormalizing sequences in two central limit theorems each reflecting different degrees of smoothness of @math . As an application to regression modelling with random design, we provide the asymptotic normality of the estimation of the linear functionals of a regression function. As a consequence of the above result, the asymptotic variance does not depend on the regression function. Finally, we debate the choice of the bandwidth for integral approximation and we highlight the good behavior of our procedure through simulations. The ( @math 1+ź) EA with mutation probability c n, where @math c>0 is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and @math ź. It turns out that 1 n is the only optimal mutation probability if @math ź=o(lnnlnlnn lnlnlnn), which is the cut-off point for linear speed-up. However, if @math ź is above this cut-off point then the standard mutation probability 1 n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The theoretical results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds. Experimental supplements shed light on the optimal mutation probability for small problem sizes. Let @math denote a random symmetric @math matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values @math and @math with probability @math each). It is widely conjectured that @math is singular with probability at most @math . On the other hand, the best known upper bound on the singularity probability of @math , due to Vershynin (2011), is @math , for some unspecified small constant @math . This improves on a polynomial singularity bound due to Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the singularity probability decays faster than any polynomial. In this paper, improving on all previous results, we show that the probability of singularity of @math is at most @math for all sufficiently large @math . The proof utilizes and extends a novel combinatorial approach to discrete random matrix theory, which has been recently introduced by the authors together with Luh and Samotij. We study the asymptotic behavior of the persistent homology of i.i.d. samples from a @math -Ahlfors regular measure --- one that satisfies uniform bounds of the form for some @math all @math in the support of @math and all sufficiently small @math Our main result is that if @math are sampled from a @math -Ahlfors regular measure on @math and @math denotes the @math -weight of the minimal spanning tree on @math [E_ (x_1, ,x_n )= e T (x_1, ,x_n ) |e|^ ] then [E_ (x_1, ,x_n ) n^ d- d ] with high probability as @math We also prove theorems about the asymptotic behavior of weighted sums defined in terms of higher-dimensional persistent homology. As an application, we exhibit hypotheses under which the fractal dimension of a measure can be computed from the persistent homology of i.i.d. samples from that space, in a manner similar to that proposed in the experimental work of (2018). Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast @math -coloring of trees requires random bits: Building on the recent lower bounds of , we prove that the randomized complexity of @math -coloring a tree with maximum degree @math is @math , whereas its deterministic complexity is @math for any @math . This also establishes a large separation between the deterministic complexity of @math -coloring and @math -coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in @math rounds can be transformed to run in @math rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires @math time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size @math is at least its deterministic complexity on instances of size @math . This shows that a deterministic @math lower bound for any problem implies a randomized @math lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model. Many NP-complete constraint satisfaction problems appear to undergo a “phase transition” from solubility to insolubility when the constraint density passes through a critical threshold. In all such cases it is easy to derive upper bounds on the location of the threshold by showing that above a certain density the first moment (expectation) of the number of solutions tends to zero. We show that in the case of certain symmetric constraints, considering the second moment of the number of solutions yields nearly matching lower bounds for the location of the threshold. Specifically, we prove that the threshold for both random hypergraph 2-colorability (Property B) and random Not-All-Equal @math -SAT is @math . As a corollary, we establish that the threshold for random @math -SAT is of order @math , resolving a long-standing open problem. Suppose that @math is a sequence of finite connected planar graphs, and in each @math a special vertex, called the root, is chosen randomly-uniformly. We introduce the notion of a distributional limit @math of such graphs. Assume that the vertex degrees of the vertices in @math are bounded, and the bound does not depend on @math . Then after passing to a subsequence, the limit exists, and is a random rooted graph @math . We prove that with probability one @math is recurrent. The proof involves the Circle Packing Theorem. The motivation for this work comes from the theory of random spherical triangulations. In this paper, we revisit the problem of finding the longest systematic-length @math for a linear minimum storage regenerating (MSR) code with optimal repair of only systematic part, for a given per-node storage capacity @math and an arbitrary number of parity nodes @math . We study the problem by following the geometric analysis of linear subspaces and operators. First, a simple quadratic bound is given, which implies that @math is the largest number of systematic nodes in the scenario. Second, an @math -based-log bound is derived, which is superior to the upper bound on log-base @math in the prior work. Finally, an explicit upper bound depending on the value of @math is introduced, which further extends the corresponding result in the literature. The sign-rank of a matrix @math with @math entries is the least rank of a real matrix @math with @math for all @math . We obtain the first exponential lower bound on the sign-rank of a function in @math . Namely, let @math . We show that the matrix @math has sign-rank @math . This in particular implies that @math , which solves a longstanding open problem in communication complexity posed by Babai, Frankl, and Simon [Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS), 1986, pp. 337-347]. Our result additionally implies a lower bound in learning theory. Specifically, let @math be functions such that every DNF formula @math of polynomial size has the representation @math for some reals @math . We prove that then @math , which essentially matches an upper bound of @math , due to Klivans and Servedio [J. Comput. System Sci., 68 (2004), pp. 303-318]. Finally, our work yields the first exponential lower bound on the size of threshold-of-majority circuits computing a function in @math . This substantially generalizes and strengthens the results of Krause and Pudlak [Theoret. Comput. Sci., 174 (1997), pp. 137-156]. We study the problem of estimating multivariate log-concave probability density functions. We prove the first sample complexity upper bound for learning log-concave densities on @math , for all @math . Prior to our work, no upper bound on the sample complexity of this learning problem was known for the case of @math . In more detail, we give an estimator that, for any @math and @math , draws @math samples from an unknown target log-concave density on @math , and outputs a hypothesis that (with high probability) is @math -close to the target, in total variation distance. Our upper bound on the sample complexity comes close to the known lower bound of @math for this problem. We resolve several fundamental questions in the area of distributed functional monitoring, initiated by Cormode, Muthukrishnan, and Yi (SODA, 2008). In this model there are @math sites each tracking their input and communicating with a central coordinator that continuously maintain an approximate output to a function @math computed over the union of the inputs. The goal is to minimize the communication. We show the randomized communication complexity of estimating the number of distinct elements up to a @math factor is @math , improving the previous @math bound and matching known upper bounds up to a logarithmic factor. For the @math -th frequency moment @math , @math , we improve the previous @math communication bound to @math . We obtain similar improvements for heavy hitters, empirical entropy, and other problems. We also show that we can estimate @math , for any @math , using @math communication. This greatly improves upon the previous @math bound of Cormode, Muthukrishnan, and Yi for general @math , and their @math bound for @math . For @math , our bound resolves their main open question. Our lower bounds are based on new direct sum theorems for approximate majority, and yield significant improvements to problems in the data stream model, improving the bound for estimating @math in @math passes from @math to @math , giving the first bound for estimating @math in @math passes of @math bits of space that does not use the gap-hamming problem. We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is @math -complete to decide whether the classical value of a non-local game is 1 or @math . Furthermore, as long as @math is small enough, this result does not depend on the gap @math . In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap @math decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of @math (proofs with two provers, one round, completeness probability @math , soundness probability @math , and commuting-operator strategies) can increase without bound as the gap @math gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class @math - @math of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap @math gets arbitrarily small. While we do not know any computable time upper bound on the class @math , a result of the first author and Vidick shows that for @math and @math , the class @math , with constant communication from the provers, is contained in @math . We give a lower bound of @math (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis. The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csiszar and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, @math , defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by @math , is an upper bound on @math . For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain Type @math condition, which is verifiable in polynomial time, guarantees that our lower bound on @math meets the @math upper bound. Thus, the PIN models satisfying our condition are @math -maximal, indicating that the upper bound @math holds with equality. This allows us to explicitly evaluate @math for such PIN models. We also give several examples of PIN models that satisfy our Type @math condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type @math condition implies that communication from all terminals (omnivocality) is needed for establishing an SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type @math condition is satisfied. However, for the source models with four or more terminals, counterexamples exist showing that the converse does not hold in general. We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all @math . This immediately implies corresponding tight bounds on the anti-ferromagnetic Potts partition function. Taking the zero-temperature limit gives new results in extremal combinatorics: the number of @math -colorings of a @math -regular graph, for any @math , is maximized by a union of @math 's. This proves the @math case of a conjecture of Galvin and Tet ali. We study the problem of learning multivariate log-concave densities with respect to a global loss function. We obtain the first upper bound on the sample complexity of the maximum likelihood estimator (MLE) for a log-concave density on @math , for all @math . Prior to this work, no finite sample upper bound was known for this estimator in more than @math dimensions. In more detail, we prove that for any @math and @math , given @math samples drawn from an unknown log-concave density @math on @math , the MLE outputs a hypothesis @math that with high probability is @math -close to @math , in squared Hellinger loss. A sample complexity lower bound of @math was previously known for any learning algorithm that achieves this guarantee. We thus establish that the sample complexity of the log-concave MLE is near-optimal, up to an @math factor. The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as @math , etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical @math -Coloring . A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the @math -level Hierarchical @math -Coloring problem is @math , for @math . The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized @math -time algorithm solving the LCL can be transformed into a deterministic @math -time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges @math --- @math or @math --- @math . 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in @math time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be @math and @math . We give a sharp lower bound on the number of matchings of a given size in a bipartite graph. When specialized to regular bipartite graphs, our results imply Friedland's Lower Matching Conjecture and Schrijver's theorem proven by Gurvits and Csikvari. Indeed, our work extends the recent work of Csikvari done for regular and bi-regular bipartite graphs. Moreover, our lower bounds are order optimal as they are attained for a sequence of @math -lifts of the original graph as well as for random @math -lifts of the original graph when @math tends to infinity. We then extend our results to permanents and subpermanents sums. For permanents, we are able to recover the lower bound of Schrijver recently proved by Gurvits using stable polynomials. Our proof is algorithmic and borrows ideas from the theory of local weak convergence of graphs, statistical physics and covers of graphs. We provide new lower bounds for subpermanents sums and obtain new results on the number of matching in random @math -lifts with some implications for the matching measure and the spectral measure of random @math -lifts as well as for the spectral measure of infinite trees. Over the past decade, physicists have developed deep but non-rigorous techniques for studying phase transitions in discrete structures. Recently, their ideas have been harnessed to obtain improved rigorous results on the phase transitions in binary problems such as random @math -SAT or @math -NAESAT (e.g., Coja-Oghlan and Panagiotou: STOC 2013). However, these rigorous arguments, typically centered around the second moment method, do not extend easily to problems where there are more than two possible values per variable. The single most intensely studied example of such a problem is random graph @math -coloring. Here we develop a novel approach to the second moment method in this problem. This new method, inspired by physics conjectures on the geometry of the set of @math -colorings, allows us to establish a substantially improved lower bound on the @math -colorability threshold. The new lower bound is within an additive @math of a simple first-moment upper bound and within @math of the physics conjecture. By comparison, the best previous lower bound left a gap of about @math , unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004]. In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially, one vertex of a graph G=(V,E) owns a piece of information which is spread iteratively to all other vertices: in each timestep t=1,2,… every informed vertex chooses a neighbor uniformly at random and informs it. The question is how many time steps are required until all vertices become informed (with high probability). For various graph classes, involved methods have been developed in order to show an upper bound of @math on the runtime of the push-algorithm, where N is the number of vertices and @math denotes the diameter of G. However, no asymptotically tight bound on the runtime based on the mixing time of random walks has been established. In this work we fill this gap by deriving an upper bound of @math , where @math denotes the mixing time of a certain random walk on G. After that we prove upper bounds that are based on certain edge expansion properties of G. However, for hypercubes neither the bound based on the mixing time nor the bounds based on edge expansion properties are tight. That is why we develop a general way to combine these two approaches by which we can deduce that the runtime of the push-algorithm is Θ(log N) on every Hamming graph.