124 citations · 146 across the 14 of their papers we have counts for
17 papers
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing
Iftach Haitner, Thomas Holenstein, Omer Reingold +2
This paper uses a variant of the notion of \emph{inaccessible entropy} (Haitner, Reingold, Vadhan and Wee, STOC 2009), to give an alternative construction and proof for the fundame…
Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem
Jan Hązła, Thomas Holenstein, Anup Rao
We study a special kind of bounds (so called forbidden subgraph bounds, cf. Feige, Verbitsky '02) for parallel repetition of multi-prover games. First, we show that forbidden subgr…
Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics
Jan Hązła, Thomas Holenstein, Elchanan Mossel
There is a common theme to some research questions in additive combinatorics and noise stability. Both study the following basic question: Let be a probability distri…
Computing the -adic Canonical Quadratic Form in Polynomial Time
Chandan Dubey, Thomas Holenstein
An -ary integral quadratic form is a formal expression in -variables , where . W…
Generating a Quadratic Forms from a Given Genus
Chandan Dubey, Thomas Holenstein
Given a non-empty genus in dimensions with determinant , we give a randomized algorithm that outputs a quadratic form from this genus. The time complexity of the algorithm i…
Upper Tail Estimates with Combinatorial Proofs
Jan Hązła, Thomas Holenstein
We study generalisations of a simple, combinatorial proof of a Chernoff bound similar to the one by Impagliazzo and Kabanets (RANDOM, 2010). In particular, we prove a randomized ve…