Roei Tell

Publication Activity (10 Years)

Years Active: 2013-2024
Publications (10 Years): 50

Top Topics

Extended Abstract

Winnow Algorithm

Top Venues

Electron. Colloquium Comput. Complex.

Comput. Complex.

Publications

Dean Doron, Edward Pyne, Roei Tell
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL. STOC (2024)
Lijie Chen, Ron D. Rothblum, Roei Tell
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?). Electron. Colloquium Comput. Complex. (2024)
Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds. J. ACM 70 (4) (2023)
Lijie Chen, Roei Tell, Ryan Williams
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Roei Tell
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems. STOC (2023)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees. STOC (2023)
Dean Doron, Roei Tell
Derandomization with Minimal Memory Footprint. CCC (2023)
Lijie Chen, Roei Tell
New ways of studying the BPP = P conjecture. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Roei Tell
Guest Column: New ways of studying the BPP = P conjecture. SIGACT News 54 (2) (2023)
Dean Doron, Edward Pyne, Roei Tell
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL. Electron. Colloquium Comput. Complex. (2023)
Dean Doron, Roei Tell
Derandomization with Minimal Memory Footprint. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Roei Tell, Ryan Williams
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. FOCS (2023)
Roei Tell
Quantified Derandomization: How to Find Water in the Ocean. Found. Trends Theor. Comput. Sci. 15 (1) (2022)
Lijie Chen, Roei Tell
When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems. Electron. Colloquium Comput. Complex. (2022)
Lijie Chen, Ron D. Rothblum, Roei Tell
Unstructured Hardness to Average-Case Randomness. Electron. Colloquium Comput. Complex. (2022)
Lijie Chen, Roei Tell
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. FOCS (2022)
Lijie Chen, Ron D. Rothblum, Roei Tell
Unstructured Hardness to Average-Case Randomness. FOCS (2022)
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees. Electron. Colloquium Comput. Complex. (2022)
Dean Doron, Amnon Ta-Shma, Roei Tell
On Hitting-Set Generators for Polynomials that Vanish Rarely. Comput. Complex. 31 (2) (2022)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. Comput. Complex. 31 (1) (2022)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits (Extended Abstract). FOCS (2022)
Roei Tell
How to Find Water in the Ocean: A Survey on Quantified Derandomization. Electron. Colloquium Comput. Complex. 28 (2021)
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Roei Tell
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost. STOC (2021)
Lijie Chen, Roei Tell
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Roei Tell
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. FOCS (2021)
Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell
Fooling Constant-Depth Threshold Circuits (Extended Abstract). FOCS (2021)
Dean Doron, Amnon Ta-Shma, Roei Tell
On Hitting-Set Generators for Polynomials That Vanish Rarely. APPROX-RANDOM (2020)
Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract. FOCS (2020)
Lijie Chen, Roei Tell
Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost. Electron. Colloquium Comput. Complex. 27 (2020)
Roei Tell
Property Testing Lower Bounds via a Generalization of Randomized Parity Decision Trees. Theory Comput. Syst. 63 (3) (2019)
Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds. Electron. Colloquium Comput. Complex. 26 (2019)
Roei Tell
/poly. Inf. Process. Lett. 152 (2019)
Lijie Chen, Roei Tell
Bootstrapping results for threshold circuits "just beyond" known lower bounds. STOC (2019)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. ITCS (2019)
Roei Tell
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. Comput. Complex. 28 (2) (2019)
Dean Doron, Amnon Ta-Shma, Roei Tell
On Hitting-Set Generators for Polynomials that Vanish Rarely. Electron. Colloquium Comput. Complex. 26 (2019)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. Electron. Colloquium Comput. Complex. 25 (2018)
Roei Tell
Lower Bounds on Black-Box Reductions of Hitting to Density Estimation. STACS (2018)
Roei Tell
Quantified derandomization of linear threshold circuits. STOC (2018)
Lijie Chen, Roei Tell
Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds. Electron. Colloquium Comput. Complex. 25 (2018)
Roei Tell
Proving that prBPP=prP is as hard as "almost" proving that P ≠ NP. Electron. Colloquium Comput. Complex. 25 (2018)
Roei Tell
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. Computational Complexity Conference (2017)
Roei Tell
Quantified Derandomization of Linear Threshold Circuits. CoRR (2017)
Roei Tell
A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization. Electron. Colloquium Comput. Complex. 24 (2017)
Roei Tell
Quantified derandomization of linear threshold circuits. Electron. Colloquium Comput. Complex. 24 (2017)
Roei Tell
On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]. ITCS (2016)
Roei Tell
A Note on Tolerant Testing with One-Sided Error. Electron. Colloquium Comput. Complex. 23 (2016)
Roei Tell
Lower Bounds on Black-Box Reductions of Hitting to Density Estimation. Electron. Colloquium Comput. Complex. 23 (2016)
Roei Tell
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. Electron. Colloquium Comput. Complex. 23 (2016)
Roei Tell
On Being Far from Far and on Dual Problems in Property Testing. Electron. Colloquium Comput. Complex. 22 (2015)
Roei Tell
Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees. Electron. Colloquium Comput. Complex. 21 (2014)
Roei Tell
An Alternative Proof of an Ω(k) Lower Bound for Testing k-linear Boolean Functions. Electron. Colloquium Comput. Complex. 21 (2014)
Roei Tell, Peter Izsak, Aidan Shribman, Steve Walsh, Benoit Hudzia
Leveraging memory mirroring for transparent memory scale-out with zero-downtime failover of remote hosts. ISCC (2013)