The UGC hardness threshold of the Lp Grothendieck problem (2009)
Guy Kindler, Assaf Naor, Gideon Schechtman
Abstract For p> = 2 we consider the problem of, given an n * n matrix A = (ai j) whose diagonal entries vanish,approximating in polynomial time the number
The Geometry of Manipulation - a Quantitative Proof of the Gibbard Satterthwaite Theorem (2009)
Isaksson, Marcus, Kindler, Guy, Mossel, Elchanan
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...
Submitted to the Senate of Tel-Aviv University (2009)
under the supervision of prof. Shmuel Safra
Spherical Cubes and Rounding in High Dimensions (2009)
Guy Kindler, Anup Rao, Avi Wigderson
What is the least surface area of a shape that tiles R d under translations by Z d? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Ω ( √ d)....
Optp (A) ≔ max ai jxixj: (x1,..., xn) ∈ R (2009)
Guy Kindler, Assaf Naor, Gideon Schechtman
For p ≥ 2 we consider the problem of, given an n × n matrix A = (ai j) whose diagonal entries vanish, approximating in polynomial time the number n�
Guy Kindler, Assaf Naor, Gideon Schechtman
hardness threshold of the ℓp Grothendieck problem
On Distributions Computable by Random Walks on Graphs * (2008)
Key words. Finite-state generator, automata, random walks on graphs, random number generation. AMS Subject Classifications. 65C10, 68Q05, 68Q70. Abstract. We answer a question raised by Donald E....
On Non-Approximability for Quadratic Programs Preliminary Version (2008)
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 ∈ {−1, +1} n that maximizes xT Ax....
Boaz Barak, Guy Kindler, Benny Sudakov, Avi Wigderson
A distribution X over binary strings of length n has minentropy k if every string has probability at most 2 −k in X. 1 We say that X is a δ-source if its rate k/n is at least δ. We give the...
Spherical Cubes and Rounding in High Dimensions (2008)
Guy Kindler, Anup Rao, Avi Wigderson
What is the least surface area of a shape that tiles R d under translations by Z d? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Ω ( √ d)....
Eldar Fischer, Guy Kindler, Dana Ron, 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...
Noise-resistant boolean-functions are juntas, prerint (2007)
We consider Boolean functions over n binary variables, and a general p-biased, product measure over the inputs. We show that if f is of low-degree, that is, so that the weight of f on the...
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz
This paper strengthens the low-error PCP characterization of NP, coming closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for membership in any NP language can be verified with...
Motivated by the study of Parallel Repetition and also by the Unique Games Conjecture, we investigate the value of the “Odd Cycle Games ” under parallel repetition. Using tools from discrete...
Irit Dinur, Guy Kindler, Ehud Friedgut
A theorem of Bourgain [4] on Fourier tails states that if f: {−1, 1} n → {−1, 1} is a booleanvalued function on the discrete cube such that for any k> 0, |S|>k ˆf(S) 2 < k...
Eliminating cycles in the discrete torus (2006)
Béla Bollobás, Imre Leader, Guy Kindler
In this paper we consider the following question: how many vertices of the discrete torus must be deleted so that no topologically nontrivial cycles remain? We look at two different edge structures...
On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)
Irit Dinur, Ehud Friedgut, Guy Kindler
In this paper we consider bounded real-valued functions over the discrete cube, f: {−1, 1} n → [−1, 1]. Such functions arise naturally in theoretical computer science, combinatorics, and the...
Abstract We prove the first non-trivial (super linear) lower bound in the noisy broadcast model, defined by El Gamal in [6]. In this model there are n + 1 processors P0, P1,..., Pn, each of which is...
On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)
Irit Dinur, Ehud Friedgut, Guy Kindler
In this paper we consider the class of bounded functions over the discrete cube, f: {−1, 1} n → [−1, 1]. Such functions arise naturally in theoretical computer science, combinatorics, and the...
On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)
Irit Dinur, Ehud Friedgut, Guy Kindler
In this paper we consider bounded real-valued functions over the discrete cube, f: {−1,1} n → [−1,1]. Such functions arise naturally in theoretical computer science, combinatorics, and the...
On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)
Irit Dinur, Ehud Friedgut, Guy Kindler
In this paper we present a sufficient condition for a bounded function f: {−1, 1} n → R to be approximable by a function which depends on few coordinates. The condition is that the Fourier...
Eliminating cycles in the discrete torus (2006)
Béla Bollobás, Imre Leader, Guy Kindler
In this paper we consider the following question: how many vertices of the discrete torus must be deleted so that no topologically nontrivial cycles remain? We look at two different edge structures...
On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)
Irit Dinur, Ehud Friedgut, Guy Kindler
In this paper we consider bounded real-valued functions over the discrete cube, f: {−1, 1} n → [−1, 1]. Such functions arise naturally in theoretical computer science, combinatorics, and the...
Hardness of approximating the closest vector problem with pre-processing (2005)
Mikhail Alekhnovich, Subhash A. Khot, Guy Kindler, Nisheeth K. Vishnoi
Abstract We show that, unless NP`DTIME(2poly log(n)), the clos-est vector problem with pre-processing, for `p norm forany p> = 1, is hard to approximate within a factor of(log n)1/p-ffl for any...
Lower bounds for the noisy broadcast problem (2005)
Navin Goyal, Michael Saks, Guy Kindler
We prove the first non-trivial (super linear) lower bound in the noisy broadcast model, defined by El Gamal in [6]. In this model there are n + 1 processors P0, P1,..., Pn, each of which is initially...
Lower bounds for the noisy broadcast problem (2005)
Navin Goyal, Michael Saks, Guy Kindler
We prove the first non-trivial (super linear) lower bound in the noisy broadcast model, defined by El Gamal in [6]. In this model there are n + 1 processors P0, P1,..., Pn, each of which is initially...
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. 1 X is called a δ-source if its rate k/n is at least δ. We give the following...
SAFRA: On non-approximability for quadratic programs (2005)
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 ∈ {−1, 1} n that maximizes x T Mx....
Hardness of approximating the closest vector problem with pre-processing (2005)
Mikhail Alekhnovich, Subhash A. Khot, Guy Kindler, Nisheeth K. Vishnoi
We show that, unless NP⊆DTIME(2 poly log(n)), the closest vector problem with pre-processing, for ℓp norm for any p ≥ 1, is hard to approximate within a factor of (log n) 1/p−ɛ for any...
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of α GW + ɛ, for all ɛ> 0; here α GW ≈.878567 denotes the...
Hardness of approximating the closest vector problem with pre-processing (2005)
Mikhail Alekhnovich, Subhash A. Khot, Guy Kindler, Nisheeth K. Vishnoi
We show that, unless NP⊆DTIME(2 poly log(n)), the closest vector problem with pre-processing, for ℓp norm for any p ≥ 1, is hard to approximate within a factor of (log n) 1/p−ǫ for any...
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of αGW + ɛ, for all ɛ> 0; here αGW ≈.878567 denotes the...
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson
We present new explicit constructions of deterministic randomness extractors, dispersers and related objects. More precisely, a distribution X over binary strings of length n is called a δ-source if...
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs (2004)
Subhash Khot, Guy Kindler, Elchanan Mossel
In this paper we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of αGW+ɛ, for all ɛ> 0, where αGW denotes the approximation ratio achieved by the...
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs (2004)
Subhash Khot, Elchanan Mossel, Guy Kindler
In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of αGW + ɛ, for all ɛ> 0; here αGW ≈.878567 denotes the...
Preliminary version Abstract (2004)
Subhash Khot, Elchanan Mossel, Guy Kindler
In this paper we give evidence that it is NP-hard to approximate MAX-CUT to within a factor of α GW+ɛ, for all ɛ> 0. Here α GW denotes the approximation ratio achieved by the...
Journal of Computer and System Sciences] (]]]])]]]–]]] (2003)
Eldar Fischer, Guy Kindler, B Dana Ron, Shmuel Safra, Alex Samorodnitsky D
Eldar Fischer Guy, Guy Kindler, Dana Ron, Alex Samorodnitsky
We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of...
Eldar Fischer Guy, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
We show that a boolean function over n 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 #. We...
PCP characterizations of NP: Towards a polynomially-small error-probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a witness for the membership of a given input...
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (1999)
Irit Dinur Eldar, Eldar Fischer, Guy Kindler, Ran Raz
this paper we show a PCP-characterization of NP of small (sub-constant) error probability. In addition, we impose additional structure on the local-readers, namely require the tests to be...
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Namely, we prove that witnesses for membership in any NP language can be...
PCP characterizations of NP: Towards a polynomially-small error-probability (1999)
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given...