Showing 1–21 of 21 results for author: Kindler, G

Polynomial Bogolyubov for special linear groups via tensor rank

Authors: Shai Evra, Guy Kindler, Noam Lifshitz

Abstract: We prove a polynomial Bogolyubov type lemma for the special linear group over finite fields. Specifically, we show that there exists an absolute constant $C>0,$ such that if $A$ is a density $α$ subset of the special linear group, then the set $AA^{-1}AA^{-1}$ contains a subgroup $H$ of density $α^C$. Moreover, this subgroup is isomorphic to a special linear group of a smaller rank. We also show t… ▽ More We prove a polynomial Bogolyubov type lemma for the special linear group over finite fields. Specifically, we show that there exists an absolute constant $C>0,$ such that if $A$ is a density $α$ subset of the special linear group, then the set $AA^{-1}AA^{-1}$ contains a subgroup $H$ of density $α^C$. Moreover, this subgroup is isomorphic to a special linear group of a smaller rank. We also show that if $A$ is an approximate subgroups then it can be covered by the union of few cosets of $H$. Our proof makes use of the Gurevich--Howe notion of tensor rank, and of a strengthened Bonami type Lemma for global functions on the bilinear scheme. We also present applications to spectral bounds for global convolution operators, global product free sets, and covering numbers corresponding to global sets. △ Less

Submitted 31 March, 2024; originally announced April 2024.

Product Mixing in Compact Lie Groups

Authors: David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer

Abstract: If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $xy=z$ has no solutions with $x,y,z \in S$. For $D \in \mathbb{N}$, a group $G$ is said to be $D$-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of $G$ is at least $D$. Gowers showed that in a $D$-quasirandom finite group $G$, the maximal size of a product-free set is at most… ▽ More If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $xy=z$ has no solutions with $x,y,z \in S$. For $D \in \mathbb{N}$, a group $G$ is said to be $D$-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of $G$ is at least $D$. Gowers showed that in a $D$-quasirandom finite group $G$, the maximal size of a product-free set is at most $|G|/D^{1/3}$. This disproved a longstanding conjecture of Babai and Sós from 1985. For the special unitary group, $G=SU(n)$, Gowers observed that his argument yields an upper bound of $n^{-1/3}$ on the measure of a measurable product-free subset. In this paper, we improve Gowers' upper bound to $\exp(-cn^{1/3})$, where $c>0$ is an absolute constant. In fact, we establish something stronger, namely, product-mixing for measurable subsets of $SU(n)$ with measure at least $\exp(-cn^{1/3})$; for this product-mixing result, the $n^{1/3}$ in the exponent is sharp. Our approach involves introducing novel hypercontractive inequalities, which imply that the non-Abelian Fourier spectrum of the indicator function of a small set concentrates on high-dimensional irreducible representations. Our hypercontractive inequalities are obtained via methods from representation theory, harmonic analysis, random matrix theory and differential geometry. We generalize our hypercontractive inequalities from $SU(n)$ to an arbitrary $D$-quasirandom compact connected Lie group for $D$ at least an absolute constant, thereby extending our results on product-free sets to such groups. We also demonstrate various other applications of our inequalities to geometry (viz., non-Abelian Brunn-Minkowski type inequalities), mixing times, and the theory of growth in compact Lie groups. △ Less

Submitted 3 May, 2024; v1 submitted 27 January, 2024; originally announced January 2024.

Comments: References updated

MSC Class: 05D05; 22E30; 20F69; 22D40; 60B15; 68Q17

Improved Monotonicity Testers via Hypercube Embeddings

Authors: Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer

Abstract: We show improved monotonicity testers for the Boolean hypercube under the $p$-biased measure, as well as over the hypergrid $[m]^n$. Our results are: 1. For any $p\in (0,1)$, for the $p$-biased hypercube we show a non-adaptive tester that makes $\tilde{O}(\sqrt{n}/\varepsilon^2)$ queries, accepts monotone functions with probability $1$ and rejects functions that are $\varepsilon$-far from monoto… ▽ More We show improved monotonicity testers for the Boolean hypercube under the $p$-biased measure, as well as over the hypergrid $[m]^n$. Our results are: 1. For any $p\in (0,1)$, for the $p$-biased hypercube we show a non-adaptive tester that makes $\tilde{O}(\sqrt{n}/\varepsilon^2)$ queries, accepts monotone functions with probability $1$ and rejects functions that are $\varepsilon$-far from monotone with probability at least $2/3$. 2. For all $m\in\mathbb{N}$, we show an $\tilde{O}(\sqrt{n}m^3/\varepsilon^2)$ query monotonicity tester over $[m]^n$. We also establish corresponding directed isoperimetric inequalities in these domains. Previously, the best known tester due to Black, Chakrabarty and Seshadhri had $Ω(n^{5/6})$ query complexity. Our results are optimal up to poly-logarithmic factors and the dependency on $m$. Our proof uses a notion of monotone embeddings of measures into the Boolean hypercube that can be used to reduce the problem of monotonicity testing over an arbitrary product domains to the Boolean cube. The embedding maps a function over a product domain of dimension $n$ into a function over a Boolean cube of a larger dimension $n'$, while preserving its distance from being monotone; an embedding is considered efficient if $n'$ is not much larger than $n$, and we show how to construct efficient embeddings in the above mentioned settings. △ Less

Submitted 16 November, 2022; originally announced November 2022.

An analogue of Bonami's Lemma for functions on spaces of linear maps, and 2-2 Games

Authors: David Ellis, Guy Kindler, Noam Lifshitz

Abstract: We prove an analogue of Bonami's (hypercontractive) lemma for complex-valued functions on $\mathcal{L}(V,W)$, where $V$ and $W$ are vector spaces over a finite field. This inequality is useful for functions on $\mathcal{L}(V,W)$ whose `generalised influences' are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra t… ▽ More We prove an analogue of Bonami's (hypercontractive) lemma for complex-valued functions on $\mathcal{L}(V,W)$, where $V$ and $W$ are vector spaces over a finite field. This inequality is useful for functions on $\mathcal{L}(V,W)$ whose `generalised influences' are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra that pseudorandom sets in Grassmann graphs have near-perfect expansion, which (in combination with the work of Dinur, Khot, Kindler, Minzer and Safra) implies the 2-2 Games conjecture (the variant, that is, with imperfect completeness). △ Less

Submitted 9 September, 2022; originally announced September 2022.

Comments: 46 pages

MSC Class: 05D05 ACM Class: F.2.2

The success probability in Levine's hat problem, and independent sets in graphs

Authors: Noga Alon, Ehud Friedgut, Gil Kalai, Guy Kindler

Abstract: Lionel Levine's hat challenge has $t$ players, each with a (very large, or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their re… ▽ More Lionel Levine's hat challenge has $t$ players, each with a (very large, or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their respective stacks. They are proclaimed successful only if they are all correct. Levine's conjecture is that the success probability tends to zero when the number of players grows. We prove that this success probability is strictly decreasing in the number of players, and present some connections to problems in graph theory: relating the size of the largest independent set in a graph and in a random induced subgraph of it, and bounding the size of a set of vertices intersecting every maximum-size independent set in a graph. △ Less

Submitted 21 August, 2023; v1 submitted 14 August, 2022; originally announced August 2022.

Comments: arXiv admin note: substantial text overlap with arXiv:2103.01541, arXiv:2103.05998

Forbidden intersection problems for families of linear maps

Authors: David Ellis, Guy Kindler, Noam Lifshitz

Abstract: We study an analogue of the Erdős-Sós forbidden intersection problem, for families of linear maps. If $V$ and $W$ are vector spaces over the same field, we say a family $\mathcal{F}$ of linear maps from $V$ to $W$ is \emph{$(t-1)$-intersection-free} if for any two linear maps $σ_1,σ_2 \in \mathcal{F}$, $\dim(\{v \in V:\ σ_1(v)=σ_2(v)\}) \neq t-1$. We prove that if $n$ is sufficiently large dependi… ▽ More We study an analogue of the Erdős-Sós forbidden intersection problem, for families of linear maps. If $V$ and $W$ are vector spaces over the same field, we say a family $\mathcal{F}$ of linear maps from $V$ to $W$ is \emph{$(t-1)$-intersection-free} if for any two linear maps $σ_1,σ_2 \in \mathcal{F}$, $\dim(\{v \in V:\ σ_1(v)=σ_2(v)\}) \neq t-1$. We prove that if $n$ is sufficiently large depending on $t$, $q$ is any prime power, $V$ is an $n$-dimensional vector space over $\mathbb{F}_q$, and $\mathcal{F} \subset \textrm{GL}(V)$ is $(t-1)$-intersection-free, then $|\mathcal{F}| \leq \prod_{i=1}^{n-t}(q^n - q^{i+t-1})$. Equality holds only if there exists a $t$-dimensional subspace of $V$ on which all elements of $\mathcal{F}$ agree, or a $t$-dimensional subspace of $V^*$ on which all elements of $\{σ^*:\ σ\in \mathcal{F}\}$ agree. Our main tool is a `junta approximation' result for families of linear maps with a forbidden intersection: namely, that if $V$ and $W$ are finite-dimensional vector spaces over the same finite field, then any $(t-1)$-intersection-free family of linear maps from $V$ to $W$ is essentially contained in a $t$-intersecting \emph{junta} (meaning, a family $\mathcal{J}$ of linear maps from $V$ to $W$ such that the membership of $σ$ in $\mathcal{J}$ is determined by $σ(v_1),\ldots,σ(v_M),σ^*(a_1),\ldots,σ^*(a_N)$, where $v_1,\ldots,v_M \in V$, $a_1,\ldots,a_N \in W^*$ and $M+N$ is bounded). The proof of this in turn relies on a variant of the `junta method' (originally introduced by Dinur and Friedgut, and powefully extended by Keller and the last author), together with spectral techniques and a hypercontractive inequality. △ Less

Submitted 11 December, 2023; v1 submitted 9 August, 2022; originally announced August 2022.

Comments: 23 pages

MSC Class: 05D05

Journal ref: Discrete Analysis 2023:19

Isoperimetric Inequalities Made Simpler

Authors: Ronen Eldan, Guy Kindler, Noam Lifshitz, Dor Minzer

Abstract: We give an alternative, simple method to prove isoperimetric inequalities over the hypercube. In particular, we show: 1. An elementary proof of classical isoperimetric inequalities of Talagrand, as well as a stronger isoperimetric result conjectured by Talagrand and recently proved by Eldan and Gross. 2. A strengthening of the Friedgut junta theorem, asserting that if the $p$-moment of the sen… ▽ More We give an alternative, simple method to prove isoperimetric inequalities over the hypercube. In particular, we show: 1. An elementary proof of classical isoperimetric inequalities of Talagrand, as well as a stronger isoperimetric result conjectured by Talagrand and recently proved by Eldan and Gross. 2. A strengthening of the Friedgut junta theorem, asserting that if the $p$-moment of the sensitivity of a function is constant for some $1/2 + \varepsilon\leq p\leq 1$, then the function is close to a junta. In this language, Friedgut's theorem is the special case that $p=1$. △ Less

Submitted 1 August, 2024; v1 submitted 13 April, 2022; originally announced April 2022.

The success probability in Lionel Levine's hat problem is strictly decreasing with the number of players, and this is related to interesting questions regarding Hamming powers of Kneser graphs and independent sets in random subgraphs

Authors: Ehud Friedgut, Gil Kalai, Guy Kindler

Abstract: Lionel Levine's hat challenge has $t$ players, each with a (very large, or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their re… ▽ More Lionel Levine's hat challenge has $t$ players, each with a (very large, or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their respective stacks. They are proclaimed successful only if they are all correct. Levine's conjecture was the success probability tends to zero when the number of players grows. We prove that this success probability is strictly decreasing in the number of players, and present some connections to questions in graph theory. △ Less

Submitted 9 March, 2021; v1 submitted 2 March, 2021; originally announced March 2021.

Hypercontractivity on the symmetric group

Authors: Yuval Filmus, Guy Kindler, Noam Lifshitz, Dor Minzer

Abstract: The hypercontractive inequality is a fundamental result in analysis, with many applications throughout discrete mathematics, theoretical computer science, combinatorics and more. So far, variants of this inequality have been proved mainly for product spaces, which raises the question of whether analogous results hold over non-product domains. We consider the symmetric group, $S_n$, one of the mo… ▽ More The hypercontractive inequality is a fundamental result in analysis, with many applications throughout discrete mathematics, theoretical computer science, combinatorics and more. So far, variants of this inequality have been proved mainly for product spaces, which raises the question of whether analogous results hold over non-product domains. We consider the symmetric group, $S_n$, one of the most basic non-product domains, and establish hypercontractive inequalities on it. Our inequalities are most effective for the class of \emph{global functions} on $S_n$, which are functions whose $2$-norm remains small when restricting $O(1)$ coordinates of the input, and assert that low-degree, global functions have small $q$-norms, for $q>2$. As applications, we show: 1. An analog of the level-$d$ inequality on the hypercube, asserting that the mass of a global function on low-degrees is very small. We also show how to use this inequality to bound the size of global, product-free sets in the alternating group $A_n$. 2. Isoperimetric inequalities on the transposition Cayley graph of $S_n$ for global functions, that are analogous to the KKL theorem and to the small-set expansion property in the Boolean hypercube. 3. Hypercontractive inequalities on the multi-slice, and stability versions of the Kruskal--Katona Theorem in some regimes of parameters. △ Less

Submitted 27 October, 2020; v1 submitted 11 September, 2020; originally announced September 2020.

Towards a quantum-inspired proof for IP = PSPACE

Authors: Ayal Green, Guy Kindler, Yupan Liu

Abstract: We explore quantum-inspired interactive proof systems where the prover is limited. Namely, we improve on a result by [AG17] showing a quantum-inspired interactive protocol ($\sf IP$) for $\sf PreciseBQP$ where the prover is only assumed to be a $\sf PreciseBQP$ machine, and show that the result can be strengthened to show an $\sf IP$ for $\sf NP^{PP}$ with a prover which is only assumed to be an… ▽ More We explore quantum-inspired interactive proof systems where the prover is limited. Namely, we improve on a result by [AG17] showing a quantum-inspired interactive protocol ($\sf IP$) for $\sf PreciseBQP$ where the prover is only assumed to be a $\sf PreciseBQP$ machine, and show that the result can be strengthened to show an $\sf IP$ for $\sf NP^{PP}$ with a prover which is only assumed to be an $\sf NP^{PP}$ machine - which was not known before. We also show how the protocol can be used to directly verify $\sf QMA$ computations, thus connecting the sum-check protocol by [AAV13] with the result of [AG17, LFKN90]. Our results shed light on a quantum-inspired proof for ${\sf IP} = {\sf PSPACE}$, as $\sf PreciseQMA$ captures the full $\sf PSPACE$ power. △ Less

Submitted 5 November, 2021; v1 submitted 25 December, 2019; originally announced December 2019.

Comments: 10 pages. Minor changes and corrections compared to v2

Journal ref: Quantum Inf. Comput. 21(5&6): 377-386 (2021)

Towards a Proof of the Fourier--Entropy Conjecture?

Authors: Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, Muli Safra

Abstract: The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is $o(\log n)$. However, both results become useless… ▽ More The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is $o(\log n)$. However, both results become useless when the total influence of the function is $ω(\log n)$. The only case in which this logarithmic barrier has been broken for an interesting class of functions was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_n$. In this paper, we build and improve on the techniques of the Bourgain-Kalai paper and establish new concentration results on the Fourier spectrum of Boolean functions with small total influence. Our results include: 1. A quantitative improvement of the Bourgain--Kalai result regarding the total influence of functions that are transitively symmetric. 2. A slightly weaker version of the Fourier--Entropy Conjecture of Friedgut and Kalai. This weaker version implies in particular that the Fourier spectrum of a constant variance, Boolean function $f$ is concentrated on $2^{O(I[f]\log I[f])}$ characters, improving an earlier result of Friedgut. Removing the $\log I[f]$ factor would essentially resolve the Fourier--Entropy Conjecture, as well as settle a conjecture of Mansour regarding the Fourier spectrum of polynomial size DNF formulas. Our concentration result has new implications in learning theory: it implies that the class of functions whose total influence is at most $K$ is agnostically learnable in time $2^{O(K\log K)}$, using membership queries. △ Less

Submitted 7 May, 2020; v1 submitted 24 November, 2019; originally announced November 2019.

Quantum automata cannot detect biased coins, even in the limit

Authors: Guy Kindler, Ryan O`Donnell

Abstract: Aaronson and Drucker (2011) asked whether there exists a quantum finite automaton that can distinguish fair coin tosses from biased ones by spending significantly more time in accepting states, on average, given an infinite sequence of tosses. We answer this question negatively. Aaronson and Drucker (2011) asked whether there exists a quantum finite automaton that can distinguish fair coin tosses from biased ones by spending significantly more time in accepting states, on average, given an infinite sequence of tosses. We answer this question negatively. △ Less

Submitted 11 October, 2016; originally announced October 2016.

Comments: preprint

Geometric stability via information theory

Authors: David Ellis, Ehud Friedgut, Guy Kindler, Amir Yehudayoff

Abstract: The Loomis-Whitney inequality, and the more general Uniform Cover inequality, bound the volume of a body in terms of a product of the volumes of lower-dimensional projections of the body. In this paper, we prove stability versions of these inequalities, showing that when they are close to being tight, the body in question is close in symmetric difference to a 'box'. Our results are best possible u… ▽ More The Loomis-Whitney inequality, and the more general Uniform Cover inequality, bound the volume of a body in terms of a product of the volumes of lower-dimensional projections of the body. In this paper, we prove stability versions of these inequalities, showing that when they are close to being tight, the body in question is close in symmetric difference to a 'box'. Our results are best possible up to a constant factor depending upon the dimension alone. Our approach is information theoretic. We use our stability result for the Loomis-Whitney inequality to obtain a stability result for the edge-isoperimetric inequality in the infinite $d$-dimensional lattice. Namely, we prove that a subset of $\mathbb{Z}^d$ with small edge-boundary must be close in symmetric difference to a $d$-dimensional cube. Our bound is, again, best possible up to a constant factor depending upon $d$ alone. △ Less

Submitted 16 January, 2017; v1 submitted 29 September, 2015; originally announced October 2015.

Comments: 28 pages. Reformatted for Discrete Analysis, but otherwise identical to the previous version

MSC Class: 52C07; 05D99 ACM Class: G.2.1

Remarks on the Most Informative Function Conjecture at fixed mean

Authors: Guy Kindler, Ryan O'Donnell, David Witmer

Abstract: In 2013, Courtade and Kumar posed the following problem: Let $\boldsymbol{x} \sim \{\pm 1\}^n$ be uniformly random, and form $\boldsymbol{y} \sim \{\pm 1\}^n$ by negating each bit of $\boldsymbol{x}$ independently with probability $α$. Is it true that the mutual information $I(f(\boldsymbol{x}) \mathbin{;} \boldsymbol{y})$ is maximized among $f:\{\pm 1\}^n \to \{\pm 1\}$ by $f(x) = x_1$? We do not… ▽ More In 2013, Courtade and Kumar posed the following problem: Let $\boldsymbol{x} \sim \{\pm 1\}^n$ be uniformly random, and form $\boldsymbol{y} \sim \{\pm 1\}^n$ by negating each bit of $\boldsymbol{x}$ independently with probability $α$. Is it true that the mutual information $I(f(\boldsymbol{x}) \mathbin{;} \boldsymbol{y})$ is maximized among $f:\{\pm 1\}^n \to \{\pm 1\}$ by $f(x) = x_1$? We do not resolve this problem. Instead, we make a couple of observations about the fixed-mean version of the conjecture. We show that Courtade and Kumar's stronger Lex Conjecture fails for small noise rates. We also prove a continuous version of the conjecture on the sphere and show that it implies the previously-known analogue for Gaussian space. △ Less

Submitted 25 January, 2016; v1 submitted 10 June, 2015; originally announced June 2015.

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

Authors: Irit Dinur, Prahladh Harsha, Guy Kindler

Abstract: We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/\text{poly}(n)$, while making at most $O(\text{poly}\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/\text{poly}\log\log n}$. Previous constructions that obtain $1/\text{poly}(n)$ soundness error used either… ▽ More We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/\text{poly}(n)$, while making at most $O(\text{poly}\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/\text{poly}\log\log n}$. Previous constructions that obtain $1/\text{poly}(n)$ soundness error used either $\text{poly}\log n $ queries or an exponential sized alphabet, i.e. of size $2^{n^c}$ for some $c>0$. Our result is an exponential improvement in both parameters simultaneously. Our result can be phrased as a polynomial-gap hardness for approximate CSPs with arity $\text{poly}\log\log n$ and alphabet size $n^{1/\text{poly}\log n}$. The ultimate goal, in this direction, would be to prove polynomial hardness for CSPs with constant arity and polynomial alphabet size (aka the sliding scale conjecture for inverse polynomial soundness error). Our construction is based on a modular generalization of previous PCP constructions in this parameter regime, which involves a composition theorem that uses an extra `consistency' query but maintains the inverse polynomial relation between the soundness error and the alphabet size. Our main technical/conceptual contribution is a new notion of soundness, which we refer to as {\em distributional soundness}, that replaces the previous notion of "list decoding soundness", and that allows us to prove a modular composition theorem with tighter parameters. This new notion of soundness allows us to invoke composition a super-constant number of times without incurring a blow-up in the soundness error. △ Less

Submitted 23 May, 2015; originally announced May 2015.

Journal ref: In Proc. 47th ACM Symp. on Theory of Computing (STOC), pages 267-276, 2015

Invariance principle on the slice

Authors: Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer

Abstract: We prove an invariance principle for functions on a slice of the Boolean cube, which is the set of all vectors {0,1}^n with Hamming weight k. Our invariance principle shows that a low-degree, low-influence function has similar distributions on the slice, on the entire Boolean cube, and on Gaussian space. Our proof relies on a combination of ideas from analysis and probability, algebra and combin… ▽ More We prove an invariance principle for functions on a slice of the Boolean cube, which is the set of all vectors {0,1}^n with Hamming weight k. Our invariance principle shows that a low-degree, low-influence function has similar distributions on the slice, on the entire Boolean cube, and on Gaussian space. Our proof relies on a combination of ideas from analysis and probability, algebra and combinatorics. Our result imply a version of majority is stablest for functions on the slice, a version of Bourgain's tail bound, and a version of the Kindler-Safra theorem. As a corollary of the Kindler-Safra theorem, we prove a stability result of Wilson's theorem for t-intersecting families of sets, improving on a result of Friedgut. △ Less

Submitted 21 February, 2016; v1 submitted 7 April, 2015; originally announced April 2015.

Comments: 36 pages

Approximation of non-boolean 2CSP

Authors: Guy Kindler, Alexandra Kolla, Luca Trevisan

Abstract: We develop a polynomial time $Ω\left ( \frac 1R \log R \right)$ approximate algorithm for Max 2CSP-$R$, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size $R$, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the be… ▽ More We develop a polynomial time $Ω\left ( \frac 1R \log R \right)$ approximate algorithm for Max 2CSP-$R$, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size $R$, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the best possible approximation up to constant factors. Previously, a $1/R$-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming (SDP) and on a novel rounding technique. The SDP that we use has an almost-matching integrality gap. △ Less

Submitted 5 April, 2015; v1 submitted 2 April, 2015; originally announced April 2015.

Gaussian Noise Sensitivity and BosonSampling

Authors: Gil Kalai, Guy Kindler

Abstract: We study the sensitivity to noise of |permanent(X)|^2 for random real and complex n x n Gaussian matrices X, and show that asymptotically the correlation between the noisy and noiseless outcomes tends to zero when the noise level is ω(1)/n. This suggests that, under certain reasonable noise models, the probability distributions produced by noisy BosonSampling are very sensitive to noise. We also s… ▽ More We study the sensitivity to noise of |permanent(X)|^2 for random real and complex n x n Gaussian matrices X, and show that asymptotically the correlation between the noisy and noiseless outcomes tends to zero when the noise level is ω(1)/n. This suggests that, under certain reasonable noise models, the probability distributions produced by noisy BosonSampling are very sensitive to noise. We also show that when the amount of noise is constant the noisy value of |permanent(X)|^2 can be approximated efficiently on a classical computer. These results seem to weaken the possibility of demonstrating quantum-speedup via BosonSampling without quantum fault-tolerance. △ Less

Submitted 8 November, 2014; v1 submitted 10 September, 2014; originally announced September 2014.

Comments: Version 2: A few corrections and additions

Unique Games on the Hypercube

Authors: Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan

Abstract: In this paper, we investigate the validity of the Unique Games Conjecture when the constraint graph is the boolean hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN$(\mathbb{Z}_2)$. We conjecture that adding triangle inequalities to the SDP provides a polynomial time algorithm to solve Unique Game… ▽ More In this paper, we investigate the validity of the Unique Games Conjecture when the constraint graph is the boolean hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN$(\mathbb{Z}_2)$. We conjecture that adding triangle inequalities to the SDP provides a polynomial time algorithm to solve Unique Games on the hypercube. △ Less

Submitted 3 May, 2014; originally announced May 2014.

Quantitative relation between noise sensitivity and influences

Authors: Nathan Keller, Guy Kindler

Abstract: A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm showed that if the sum of squares of influences in $f$ is close to zero then $f$ must be noise sensitive. We show a quantitative version of this result which does not depend on $n$, and prove… ▽ More A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm showed that if the sum of squares of influences in $f$ is close to zero then $f$ must be noise sensitive. We show a quantitative version of this result which does not depend on $n$, and prove that it is tight for certain parameters. Our results hold also for a general product measure $μ_p$ on the discrete cube, as long as $\log 1/p \ll \log n$. We note that in [BKS], a quantitative relation between the sum of squares of the influences and the noise sensitivity was also shown, but only when the sum of squares is bounded by $n^{-c}$ for a constant $c$. Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions. In order to achieve it, we present a considerably shorter proof of Talagrand's lemma, which easily generalizes in various directions, including non-monotone functions. △ Less

Submitted 9 March, 2010; originally announced March 2010.

Comments: 20 pages

MSC Class: 05D40; 60C05; 06E30

The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem

Authors: Marcus Isaksson, Guy Kindler, Elchanan Mossel

Abstract: We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function f of $q \ge 4$ alternatives and n voters will be manipulable with probability at least $10^{-4} \eps^2 n^{-3} q^{-30}$, where $\eps$ is the minimal statistical distance between f and the family of dictator functions. Our results extend those of Fr… ▽ More We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function f of $q \ge 4$ alternatives and n voters will be manipulable with probability at least $10^{-4} \eps^2 n^{-3} q^{-30}$, where $\eps$ is the minimal statistical distance between f and the family of dictator functions. Our results extend those of FrKaNi:08, which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in BarthOrline:91, ConitzerS03b, ElkindL05, ProcacciaR06 and ConitzerS06) cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies. △ Less

Submitted 12 April, 2010; v1 submitted 3 November, 2009; originally announced November 2009.