Arrow Research search

Author name cluster

Guy Kindler

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
1 author row

Possible papers

20

STOC Conference 2023 Conference Paper

An Analogue of Bonami's Lemma for Functions on Spaces of Linear Maps, and 2-2 Games

  • David Ellis
  • Guy Kindler
  • Noam Lifshitz

We prove an analogue of Bonami’s (hypercontractive) lemma for complex-valued functions on L (𝑉,𝑊 ), where 𝑉 and 𝑊 are vector spaces over a finite field. This inequality is useful for functions on L (𝑉,𝑊 ) 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)

Details

FOCS Conference 2020 Conference Paper

Towards a Proof of the Fourier-Entropy Conjecture?

  • Esty Kelman
  • Guy Kindler
  • Noam Lifshitz
  • Dor Minzer
  • Muli Safra

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 $\omega(\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. Our result establishes new bounds on the Fourier entropy of a Boolean function $f$, as well as stronger bounds on the Fourier entropy of low-degree parts of $f$. In particular, it implies 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 for the Fourier spectrum of functions with small total influence also has new implications in learning theory. More specifically, we conclude 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. Thus, the class of functions with total influence $O(\log n/\log\log n)$ is agnostically learnable in $\text{poly}(n)$ time.

Details

STOC Conference 2018 Conference Paper

On non-optimally expanding sets in Grassmann graphs

  • Irit Dinur
  • Subhash Khot
  • Guy Kindler
  • Dor Minzer
  • Muli Safra

We study the structure of non-expanding sets in the Grassmann graph. We put forth a hypothesis stating that every small set whose expansion is smaller than 1−δ must be correlated with one of a specified list of sets which are isomorphic to smaller Grassmann graphs. We develop a framework of Fourier analysis for analyzing functions over the Grassmann graph, and prove that our hypothesis holds for all sets whose expansion is below 7/8. In the companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018], the authors show that a linearity agreement hypothesis implies an NP-hardness gap of 1/2− vs for unique games and other inapproximability results. In [Barak, Kothari and Steurer, ECCC TR18-077], the authors show that the hypothesis in this work implies the linearity agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018]. Combined with our main theorem here this proves a version of the linearity agreement hypothesis with certain specific parameters. Short of proving the entire hypothesis, this nevertheless suffices for getting new unconditional NP hardness gaps for label cover with 2-to-1 and unique constraints. Our Expansion Hypothesis has been subsequently proved in its full form [Khot, Minzer and Safra, ECCC TR18-006] thereby proving the agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] and completing the proof of the 2-to-1 Games Conjecture (albeit with imperfect completeness).

Details

STOC Conference 2018 Conference Paper

Towards a proof of the 2-to-1 games conjecture?

  • Irit Dinur
  • Subhash Khot
  • Guy Kindler
  • Dor Minzer
  • Muli Safra

We present a polynomial time reduction from gap-3LIN to label cover with 2-to-1 constraints. In the “yes” case the fraction of satisfied constraints is at least 1 −ε, and in the “no” case we show that this fraction is at most ε, assuming a certain (new) combinatorial hypothesis on the Grassmann graph. In other words, we describe a combinatorial hypothesis that implies the 2-to-1 conjecture with imperfect completeness. The companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] makes some progress towards proving this hypothesis. Our work builds on earlier work by a subset of the authors [Khot, Minzer and Safra, STOC 2017] where a slightly different hypothesis was used to obtain hardness of approximating vertex cover to within factor of √2−ε. The most important implication of this work is (assuming the hypothesis) an NP-hardness gap of 1/2−ε vs. ε for unique games . In addition, we derive optimal NP-hardness for approximating the max-cut-gain problem, NP-hardness of coloring an almost 4-colorable graph with any constant number of colors, and the same √2−ε NP-hardness for approximate vertex cover that was already obtained based on a slightly different hypothesis. Recent progress towards proving our hypothesis [Barak, Kothari and Steurer, ECCC TR18-077], [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] directly implies some new unconditional NP-hardness results. These include new points of NP-hardness for unique games and for 2-to-1 and 2-to-2 games. More recently, the full version of our hypothesis was proven [Khot, Minzer and Safra, ECCC TR18-006].

Details

FOCS Conference 2010 Conference Paper

The Geometry of Manipulation: A Quantitative Proof of the Gibbard-Satterthwaite Theorem

  • Marcus Isaksson
  • Guy Kindler
  • Elchanan Mossel

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 \geq 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 Fried gut et al, which were obtained for the case of $3$ alternatives, and imply that the approach of masking manipulations behind computational hardness 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.

Details

FOCS Conference 2008 Conference Paper

Spherical Cubes and Rounding in High Dimensions

  • Guy Kindler
  • Ryan O'Donnell
  • Anup Rao 0001
  • Avi Wigderson

What is the least surface area of a shape that tiles Ropf d under translations by Zopf d? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Omega(radicd). Our main result is a construction with surface area O(radicd), matching the lower bound up to a constant factor of 2radic2pi/eap3. The best previous tile known was only slightly better than the cube, having surface area on the order of d. We generalize this to give a construction that tiles Ropf d by translations of any full rank discrete lattice Lambda with surface area 2piparV -1 par fb, where V is the matrix of basis vectors of Lambda, and par. par fb denotes the Frobenius norm. We show that our bounds are optimal within constant factors for rectangular lattices. Our proof is via a random tessellation process, following recent ideas of Raz in the discrete setting. Our construction gives an almost optimal noise-resistant rounding scheme to round points in Ropf d to rectangular lattice points.

Details

FOCS Conference 2005 Conference Paper

Hardness of Approximating the Closest Vector Problem with Pre-Processing

  • Michael Alekhnovich
  • Subhash Khot
  • Guy Kindler
  • Nisheeth K. Vishnoi

We show that, unless NP/spl sube/DTIME(2/sup poly log(n)/) the closest vector problem with pre-processing, for /spl lscr//sub p/ norm for any p /spl ges/ 1, is hard to approximate within a factor of (log n)/sup 1/p - /spl epsi//' /P for any /spl epsi/ > 0. This improves the previous best factor of 3/sup 1/p/ - /spl epsi/ due to Regev (2004). Our results also imply that under the same complexity assumption, the nearest codeword problem with pre-processing is hard to approximate within a factor of (log n)/sup 1 - /spl epsi//' for any /spl epsi/ > 0.

Details

FOCS Conference 2005 Conference Paper

Lower Bounds for the Noisy Broadcast Problem

  • Navin Goyal
  • Guy Kindler
  • Michael E. Saks

We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model of distributed computation. In this model, there are n + 1 processors P/sub 0/, P/sub 1/, .. ., P/sub n/. Each P/sub i/, for i /spl ges/ 1, initially has a private bit x/sub i/ and the goal is for P/sub 0/ to learn f (x/sub l/, .. ., x/sub n/) for some specified function f. At each time step, a designated processor broadcasts some function of its private bit and the bits it has heard so far. Each broadcast is received by the other processors but each reception may be corrupted by noise. In this model, Gallager (1988) gave a noise-resistant protocol that allows P/sub 0/ to learn the entire input in O(n log log n) broadcasts. We prove that Gallager's protocol is optimal up to a constant factor. Our lower bound follows from a lower bound in a new model, the generalized noisy decision tree model, which may be of independent interest.

Details

FOCS Conference 2005 Conference Paper

On Non-Approximability for Quadratic Programs

  • Sanjeev Arora
  • Eli Berger
  • Elad Hazan
  • Guy Kindler
  • Muli Safra

This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ that maximizes x/sup T/Mx. This problem recently attracted attention due to its application in various clustering settings, as well as an intriguing connection to the famous Grothendieck inequality. It is approximable to within a factor of O(log n), and known to be NP-hard to approximate within any factor better than 13/11 - /spl epsi/ for all /spl epsi/ > 0. We show that it is quasi-NP-hard to approximate to a factor better than O(log/sup /spl gamma// n)for some /spl gamma/ > 0. The integrality gap of the natural semidefinite relaxation for this problem is known as the Grothendieck constant of the complete graph, and known to be /spl Theta/(log n). The proof of this fact was nonconstructive, and did not yield an explicit problem instance where this integrality gap is achieved. Our techniques yield an explicit instance for which the integrality gap is /spl Omega/ (log n/log log n), essentially answering one of the open problems of Alon et al. [AMMN].

Details

STOC Conference 2005 Conference Paper

Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors

  • Boaz Barak
  • Guy Kindler
  • Ronen Shaltiel
  • Benny Sudakov
  • Avi Wigderson

A distribution X over binary strings of length n has min-entropy k if every string has probability at most 2 - k in X . We say that X is a δ-source if its rate k ⁄ n is at least δ.We give the following new explicit instructions (namely, poly(n)- time computable functions) of deterministic extractors, dispersers and related objects. All work for any fixed rate δ>0. No previous explicit construction was known for either of these, for any δ‹1⁄2. The first two constitute major progress to very long-standing open problems. Bipartite Ramsey f 1 : (0,1) n ) 2 →0,1, such that for any two independent δ-sources X 1 , X 2 we have f 1 ( X 1 , X 2 ) = 0,1 This implies a new explicit construction of 2N -vertex bipartite graphs where no induced N δ by N δ subgraph is complete or empty. Multiple source extraction f 2 : (0,1 n ) 3 →0,1 such that for any three independent δ-sources X 1 , X 2 , X 3 we have that f 2 ( X 1 , X 2 , X 3 ) is ( o (1)-close to being) an unbiased random bit. Constant seed condenser 2 f 3 : n →(0,1 m ) c , such that for any δ-source X , one of the c output distributions f 3 ( X ) i , is a 0.9-source over 0,1 m . Here c is a constant depending only on δ. Subspace Ramsey f 4: 0,1 n →0,1 such that for any affine -δ-source 3 X we have f 4 ( X )= 0,1.

Details

FOCS Conference 2004 Conference Paper

Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?

  • Subhash Khot
  • Guy Kindler
  • Elchanan Mossel
  • Ryan O'Donnell

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of /spl alpha//sub cw/+ /spl epsi/, for all /spl epsi/ > 0, where /spl alpha//sub cw/ denotes the approximation ratio achieved by the Goemans-Williamson algorithm (1995). /spl alpha//sub cw/ /spl ap/. 878567. This result is conditional, relying on two conjectures: a) the unique games conjecture of Khot; and, b) a very believable conjecture we call the majority is stablest conjecture. These results indicate that the geometric nature of the Goemans-Williamson algorithm might be intrinsic to the MAX-CUT problem. The same two conjectures also imply that it is NP-hard to (/spl beta/ + /spl epsi/)-approximate MAX-2SAT, where /spl beta/ /spl ap/. 943943 is the minimum of (2 + (2//spl pi/) /spl theta/)/(3 - cos(/spl theta/)) on (/spl pi//2, /spl pi/). Motivated by our proof techniques, we show that if the MAX-2CSP and MAX-2SAT problems are slightly restricted - in a way that seems to retain all their hardness -then they have (/spl alpha//sub GW/-/spl epsi/)- and (/spl beta/ - /spl epsi/)-approximation algorithms, respectively. Though we are unable to prove the majority is stablest conjecture, we give some partial results and indicate possible directions of attack. Our partial results are enough to imply that MAX-CUT is hard to (3/4 + 1/(2/spl pi/) + /spl epsi/)-approximate (/spl ap/. 909155), assuming only the unique games conjecture. We also discuss MAX-2CSP problems over non-Boolean domains and state some related results and conjectures. We show, for example, that the unique games conjecture implies that it is hard to approximate MAX-2LIN(q) to within any constant factor.

Details

FOCS Conference 2002 Conference Paper

Testing Juntas

  • Eldar Fischer
  • Guy Kindler
  • Dana Ron
  • Muli Safra
  • Alex Samorodnitsky

We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter /spl epsi/. We present two tests, both non-adaptive, that require a number of queries that is polynomial k and linear in /spl epsi//sup -1/. The first test is stronger in that it has a 1-sided error, while the second test has a more compact analysis. We also present an adaptive version and a 2-sided error version of the first test, that have a somewhat better query complexity than the other algorithms. We then provide a lower bound of /spl Omega//spl tilde/(/spl radic/ k) on the number of queries required for the non-adaptive testing of the above property; a lower bound of /spl Omega/(log(k + 1)) for adaptive algorithms naturally follows from this. In providing this we also prove a result about random walks on the group Z/sub 2//sup q/ that may be interesting in its own right. We show that for some t(q) = O/spl tilde/(q/sup 2/), the distributions of the random walk at times t and t + 2 are close to each other, independently of the step distribution of the walk. We also discuss related questions. In particular, when given in advance a known k junta function h, we show how to test a function f for the property of being identical to h up to a permutation of the variables, in a number of queries that is polynomial in k and /spl epsi/.

Details