Roei Tell

According to our database, Roei Tell authored at least 33 papers between 2013 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds.

Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev

J. ACM, August, 2023

Guest Column: New ways of studying the BPP = P conjecture.

Lijie Chen, Roei Tell

SIGACT News, 2023

Derandomization with Minimal Memory Footprint.

Dean Doron, Roei Tell

Electron. Colloquium Comput. Complex., 2023

Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL.

Dean Doron, Edward Pyne, Roei Tell

Electron. Colloquium Comput. Complex., 2023

New ways of studying the BPP = P conjecture.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2023

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization.

Lijie Chen, Roei Tell, Ryan Williams

Electron. Colloquium Comput. Complex., 2023

2022

Quantified Derandomization: How to Find Water in the Ocean.

Roei Tell

Found. Trends Theor. Comput. Sci., 2022

Depth-d Threshold Circuits vs. Depth-(d + 1) AND-OR Trees.

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

Electron. Colloquium Comput. Complex., 2022

When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2022

Unstructured Hardness to Average-Case Randomness.

Lijie Chen, Ron D. Rothblum, Roei Tell

Electron. Colloquium Comput. Complex., 2022

Expander-Based Cryptography Meets Natural Proofs.

Igor C. Oliveira, Rahul Santhanam, Roei Tell

Comput. Complex., 2022

On Hitting-Set Generators for Polynomials that Vanish Rarely.

Dean Doron, Amnon Ta-Shma, Roei Tell

Comput. Complex., 2022

2021

How to Find Water in the Ocean: A Survey on Quantified Derandomization.

Roei Tell

Electron. Colloquium Comput. Complex., 2021

Fooling Constant-Depth Threshold Circuits.

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

Electron. Colloquium Comput. Complex., 2021

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2021

Fooling Constant-Depth Threshold Circuits (Extended Abstract).

Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

A Note on Tolerant Testing with One-Sided Error.

Roei Tell

Proceedings of the Computational Complexity and Property Testing, 2020

Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2020

On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds: Extended Abstract.

Lijie Chen, Ron D. Rothblum, Roei Tell, Eylon Yogev

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Property Testing Lower Bounds via a Generalization of Randomized Parity Decision Trees.

Roei Tell

Theory Comput. Syst., 2019

Proving that <i>prBPP</i> = <i>prP</i> is as hard as proving that "almost <i>NP</i>" is not contained in <i>P</i>/poly.

Roei Tell

Inf. Process. Lett., 2019

Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials.

Roei Tell

Comput. Complex., 2019

2018

Proving that prBPP=prP is as hard as "almost" proving that P ≠ NP.

Roei Tell

Electron. Colloquium Comput. Complex., 2018

Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2018

2017

A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization.

Roei Tell

Electron. Colloquium Comput. Complex., 2017

Quantified derandomization of linear threshold circuits.

Roei Tell

Electron. Colloquium Comput. Complex., 2017

2016

Lower Bounds on Black-Box Reductions of Hitting to Density Estimation.

Roei Tell

Electron. Colloquium Comput. Complex., 2016

A Note on Tolerant Testing with One-Sided Error.

Roei Tell

Electron. Colloquium Comput. Complex., 2016

On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract].

Roei Tell

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

2015

On Being Far from Far and on Dual Problems in Property Testing.

Roei Tell

Electron. Colloquium Comput. Complex., 2015

2014

Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees.

Roei Tell

Electron. Colloquium Comput. Complex., 2014

An Alternative Proof of an Ω(k) Lower Bound for Testing k-linear Boolean Functions.

Roei Tell

Electron. Colloquium Comput. Complex., 2014

2013

Leveraging memory mirroring for transparent memory scale-out with zero-downtime failover of remote hosts.

Roei Tell, Peter Izsak, Aidan Shribman, Steve Walsh, Benoit Hudzia

Proceedings of the 2013 IEEE Symposium on Computers and Communications, 2013