Roei Tell

According to our database, Roei Tell authored at least 40 papers between 2013 and 2025.

Collaborative distances:

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

2025

Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems.

Oded Goldreich, Roei Tell

Electron. Colloquium Comput. Complex., 2025

When Connectivity Is Hard, Random Walks Are Easy with Non-determinism.

Dean Doron, Edward Pyne, Roei Tell, R. Ryan Williams

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Polynomial-Time PIT from (Almost) Necessary Assumptions.

Robert Andrews, Deepanshu Kush, Roei Tell

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?).

Lijie Chen, Ron D. Rothblum, Roei Tell

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Towards Free Lunch Derandomization from Necessary Assumptions (And OWFs).

Marshall Ball, Lijie Chen, Roei Tell

Proceedings of the 40th Computational Complexity Conference, 2025

2024

On defining PPT-search problems and PPT-optimization problems.

Roei Tell

Electron. Colloquium Comput. Complex., 2024

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

Dean Doron, Edward Pyne, Roei Tell

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness.

Jiatu Li, Edward Pyne, Roei Tell

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

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

Lijie Chen, Roei Tell

SIGACT News, 2023

New ways of studying the BPP = P conjecture.

Lijie Chen, Roei Tell

Electron. Colloquium Comput. Complex., 2023

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

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

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems.

Lijie Chen, Roei Tell

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization.

Lijie Chen, Roei Tell, Ryan Williams

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Derandomization with Minimal Memory Footprint.

Dean Doron, Roei Tell

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Quantified Derandomization: How to Find Water in the Ocean.

Roei Tell

Found. Trends Theor. Comput. Sci., 2022

Unstructured Hardness to Average-Case Randomness.

Lijie Chen, Ron D. Rothblum, Roei Tell

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 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

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

Lijie Chen, Roei Tell

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 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

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

Lijie Chen, 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

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

On Hitting-Set Generators for Polynomials That Vanish Rarely.

Dean Doron, Amnon Ta-Shma, Roei Tell

Proceedings of the Approximation, 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

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

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

Electron. Colloquium Comput. Complex., 2019

Bootstrapping results for threshold circuits "just beyond" known lower bounds.

Lijie Chen, Roei Tell

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Expander-Based Cryptography Meets Natural Proofs.

Igor Carboni Oliveira, Rahul Santhanam, Roei Tell

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

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

Roei Tell

Electron. Colloquium Comput. Complex., 2018

Quantified derandomization of linear threshold circuits.

Roei Tell

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

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

Roei Tell

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

2017

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

Roei Tell

Electron. Colloquium Comput. Complex., 2017

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

Roei Tell

Proceedings of the 32nd Computational Complexity Conference, 2017

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