Roei Tell
YOU?
Author Swipe
View article: Polynomial-Time PIT from (Almost) Necessary Assumptions
Polynomial-Time PIT from (Almost) Necessary Assumptions Open
The celebrated result of Kabanets and Impagliazzo (Computational Complexity, 2004) showed that PIT algorithms imply circuit lower bounds, and vice versa. Since then it has been a major challenge to understand the precise connections betwee…
View article: Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL Open
We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation. Our first contribution is a derandomization of bounded-space m…
View article: Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees Open
For any n ∈ ℕ and d = o(loglog(n)), we prove that there is a Boolean function F on n bits and a value γ = 2−Θ(d) such that F can be computed by a uniform depth-(d + 1) AC0 circuit with O(n) wires, but F cannot be computed by any depth-d TC…
View article: On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds Open
The Exponential-Time Hypothesis (ETH) is a strengthening of the 𝒫 ≠ 𝒩𝒫 conjecture, stating that 3- SAT on n variables cannot be solved in (uniform) time 2 εċ n , for some ε > 0. In recent years, analogous hypotheses that are “exponentially…
View article: Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost Open
Extending the classical “hardness-to-randomness” line-of-works, Doron, Moshkovitz, Oh, and Zuckerman (FOCS 2020) recently proved that derandomization with near-quadratic time overhead is possible, under the assumption that there exists a f…
View article: On Hitting-Set Generators for Polynomials That Vanish Rarely
On Hitting-Set Generators for Polynomials That Vanish Rarely Open
The problem of constructing hitting-set generators for polynomials of low degree is fundamental in complexity theory and has numerous well-known applications. We study the following question, which is a relaxation of this problem: Is it ea…
View article: Expander-Based Cryptography Meets Natural Proofs
Expander-Based Cryptography Meets Natural Proofs Open
We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or…
View article: Quantified derandomization of linear threshold circuits
Quantified derandomization of linear threshold circuits Open
One of the prominent current challenges in complexity theory is the attempt to prove lower bounds for $TC^0$, the class of constant-depth, polynomial-size circuits with majority gates. Relying on the results of Williams (2013), an appealin…
View article: Lower Bounds on Black-Box Reductions of Hitting to Density Estimation
Lower Bounds on Black-Box Reductions of Hitting to Density Estimation Open
Consider a deterministic algorithm that tries to find a string in an unknown set S\subseteq{0,1}^n, under the promise that S has large density. The only information that the algorithm can obtain about S is estimates of the density of S in …
View article: Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials Open
This work studies the question of quantified derandomization, which was introduced by Goldreich and Wigderson (STOC 2014). The generic quantified derandomization problem is the following: For a circuit class cal{C} and a parameter B=B(n), …