Thomas Holenstein

FOCS Conference 2012 Conference Paper

Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls

• Thomas Holenstein
• Makrand Sinha

We show that a black-box construction of a pseudorandom generator from a one-way function needs to make Ω(n/log(n)) calls to the underlying one-way function. The bound even holds if the one-way function is guaranteed to be regular. In this case it matches the best known construction due to Gold Reich, Krawczyk, and Luby (SIAM J. Comp. 22, 1993), which uses O(n/log(n)) calls.

SODA Conference 2011 Conference Paper

Subsampling Mathematical Relaxations and Average-case Complexity

• Boaz Barak
• Moritz Hardt
• Thomas Holenstein
• David Steurer

We initiate a study of when the value of mathematical relaxations such as linear and semi-definite programs for constraint satisfaction problems (CSPs) is approximately preserved when restricting the instance to a sub-instance induced by a small random subsample of the variables. Let C be a family of CSPs such as 3SAT, Max-Cut, etc. , and let П be a mathematical program that is a relaxation for C, in the sense that for every instance P ∊ C, П( P ) is a number in [0, 1] upper bounding the maximum fraction of satisfiable constraints of P. Loosely speaking, we say that subsampling holds for C and П if for every sufficiently dense instance P ∊ C and every ε > 0, if we let P′ be the instance obtained by restricting P to a sufficiently large constant number of variables, then П( P′ ) ∊ (1 ± ε)П( P ). We say that weak subsampling holds if the above guarantee is replaced with П( P′ ) = 1 − Θ(γ) whenever П( P ) = 1 − γ, where Θ hides only absolute constants. We obtain both positive and negative results, showing that: 1. Subsampling holds for the BasicLP and BasicSDP programs. BasicSDP is a variant of the semi-definite program considered by Raghavendra (2008), who showed it gives an optimal approximation factor for every constraint-satisfaction problem under the unique games conjecture. BasicLP is the linear programming analog of BasicSDP. 2. For tighter versions of BasicSDP obtained by adding additional constraints from the Lasserre hierarchy, weak subsampling holds for CSPs of unique games type. 3. There are non-unique CSPs for which even weak subsampling fails for the above tighter semi-definite programs. Also there are unique CSPs for which (even weak) subsampling fails for the Sherali-Adams linear programming hierarchy. As a corollary of our weak subsampling for strong semi-definite programs, we obtain a polynomial-time algorithm to certify that random geometric graphs (of the type considered by Feige and Schechtman, 2002) of max-cut value 1 − γ have a cut value at most 1 − γ/10. More generally, our results give an approach to obtaining average-case algorithms for CSPs using semi-definite programming hierarchies.

STOC Conference 2011 Conference Paper

The equivalence of the random oracle model and the ideal cipher model, revisited

• Thomas Holenstein
• Robin Künzler
• Stefano Tessaro

SODA Conference 2008 Conference Paper

Trace reconstruction with constant deletion probability and related results

• Thomas Holenstein
• Michael Mitzenmacher
• Rina Panigrahy
• Udi Wieder

STOC Conference 2007 Conference Paper

Parallel repetition: simplifications and the no-signaling case

• Thomas Holenstein

Consider a game where a refereed chooses (x,y) according to a publiclyknown distribution P X Y, sends x to Alice, and y to Bob. Withoutcommunicating with each other, Alice responds with a value "a" and Bobresponds with a value "b". Alice and Bob jointly win if a publiclyknown predicate Q(x,y,a,b) holds. Let such a game be given and assume that the maximum probabilitythat Alice and Bob can win is v<1. Raz (SIAM J. Comput. 27, 1998)shows that if the game is repeated n times in parallel, then the probability that Alice and Bob win all games simultaneously is at most v' (n/log(s)) , where s is the maximal number of possible responses from Alice and Bob in the initial game, and v' is a constant depending only on v. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication among them.

STOC Conference 2005 Conference Paper

Key agreement from weak bit agreement

• Thomas Holenstein

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S A and S B , respectively, such that with probability 1+ε/2 these bits are equal. Further assume that conditioned on the event S A =n S B no polynomial time bounded algorithm can predict the bit better than with probability 1-δ/2. Is it possible to obtain key agreement from such a primitive? We show that for constant δ and ε the answer is yes if and only if δ > 1-ε/1+ε, both for uniform and non-uniform adversaries.The main computational technique used in this paper is a strengthening of Impagliazzo's hard-core lemma to the uniform case and to a set size parameter which is tight (i.e., twice the original size). This may be of independent interest.