Roei Tell

University of Toronto — Canada

Computer Science · Physical Sciences

6h-index112citations40works1.52yr avg
OpenAlex↗ORCID↗Google Scholar↗Lab page↗

Accepting Students?

No reports yet. Know if this professor is taking students?

Research Topics

Complexity and Algorithms in Graphs(30), Cryptography and Data Security(18), Machine Learning and Algorithms(9), Advanced Graph Theory Research(8), Optimization and Search Problems(5)

Publications40 total

Polynomial-Time PIT from (Almost) Necessary Assumptions
2025Open Access
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)
2025· 2 cited
When Connectivity Is Hard, Random Walks Are Easy with Non-determinism
2025
Hardness vs. Randomness, Revised: Uniform, Non-Black-Box, and Instance-wise
SIAM Journal on Computing·2024
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
2024· 2 cited
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL=L That Uses Properties of BPL
2024· 5 citedOpen Access
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization
2023· 8 cited
Guest Column: New ways of studying the BPP = P conjecture
ACM SIGACT News·2023· 5 cited
When Arthur Has Neither Random Coins Nor Time to Spare: Superfast Derandomization of Proof Systems
2023· 10 cited
Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees
2023· 2 citedOpen Access
On Exponential-time Hypotheses, Derandomization, and Circuit Lower Bounds
Journal of the ACM·2023· 7 citedOpen Access
On Hitting-Set Generators for Polynomials that Vanish Rarely
Computational Complexity·2022
Unstructured Hardness to Average-Case Randomness
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)·2022· 7 cited
Expander-Based Cryptography Meets Natural Proofs
Computational Complexity·2022· 1 citedOpen Access
Fooling Constant-Depth Threshold Circuits (Extended Abstract)
2022· 2 cited
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
2022· 17 cited
Quantified Derandomization: How to Find Water in the Ocean
Foundations and Trends® in Theoretical Computer Science·2022· 3 citedOpen Access
Quantified Derandomization: How to Find Water in the Ocean
2022
Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
2021· 3 citedOpen Access
How to Find Water in the Ocean: A Survey on Quantified Derandomization.
Electron. Colloquium Comput. Complex.·2021· 1 cited
page 1 of 2Next →

Frequent Co-authors

Lijie Chen(10), Ron D. Rothblum(4), Dean Doron(4), Edward Pyne(3), Pooya Hatami(3), William M. Hoza(3), Avishay Tal(3), Ryan Williams(2), Eylon Yogev(2), Igor Carboni Oliveira(2), Rahul Santhanam(2), Amnon Ta‐Shma(2), Jiatu Li(1), Peter Izsak(1), Aidan Shribman(1), Steve Walsh(1), Benoît Hudzia(1), Robert Andrews(1), Deepanshu Kush(1), Lijie Chen(1)