publications and preprints
publications and preprints
Embedded Files
The papers below are listed by order of online appearance.
The papers below are listed by order of online appearance.
If you have any questions or thoughts, you're welcome to contact me. And please don't hesitate to ask questions that might seem silly to you - I'll be happy to discuss. You can also see my expositions page if you're interested.
2025.06.19 dptw.pdfWhen Connectivity is Hard, Random Walks are Easy With Non-Determinism
When Connectivity is Hard, Random Walks are Easy With Non-Determinism
with Dean Doron , Ted Pyne, and Ryan Williams
STOC 2025
Polynomial-Time PIT from (Almost) Necessary Assumptions
Polynomial-Time PIT from (Almost) Necessary Assumptions
with Robert Andrews and Deepanshu Kush
STOC 2025
Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems
Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems
with Oded Goldreich
2025.08.07 CCC.pdfTowards Free Lunch Derandomization from Necessary Assumptions (and OWFs)
Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs)
with Marshall Ball and Lijie Chen
CCC 2025
On defining PPT-search problems and PPT-optimization problems
On defining PPT-search problems and PPT-optimization problems
(joint project with Oded Goldreich; see his companion paper)
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
FOCS 2024
2025.06.11 stoc video.pdfFiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)
with Lijie Chen and Ron Rothblum
STOC 2025
2024.04.18 Simons DPT.pdfOpening 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
with Dean Doron and Ted Pyne
STOC 2024
[ECCC, Dec 2023], [Ted's talk at Brown, Feb 2024], [Ted's talk at STOC, Jun 2024]
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization
with Lijie Chen and Ryan Williams
FOCS 2023
FOCS (Nov 2022).pdf2023.06.08 stoc hhtt.pdfDepth-d Threshold Circuits vs Depth-(d+1) AND-OR Trees
Depth-d Threshold Circuits vs Depth-(d+1) AND-OR Trees
with William Hoza, Pooya Hatami, and Avishay Tal
STOC 2023
UK Complexity (July 2022).pdfWhen Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems
When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems
with Lijie Chen
STOC 2023
[ECCC, Apr 2022], [Partial video (only the second half was recorded) from IAS, Oct 2022], [Video at STOC, Jun 2023]
How to Find Water in the Ocean: A Survey on Quantified Derandomization
How to Find Water in the Ocean: A Survey on Quantified Derandomization
Foundations and Trends in TCS 2022
H2R (Sep 2021).pdfHardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
with Lijie Chen
FOCS 2021; SICOMP special issue
[ECCC, Jun 2021], [Video at FOCS, Feb 2022], [Video at TCS+, Mar 2022]
2022.02.07 hhtt.pdfFooling Constant-Depth Threshold Circuits
Fooling Constant-Depth Threshold Circuits
with William Hoza, Pooya Hatami, and Avishay Tal
FOCS 2021
[ECCC, Jan 2021], [William's TCS+ talk, Feb 2021], [Video at FOCS, Feb 2022]
Harvard (March 2021).pdfSimple 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
with Lijie Chen
STOC 2021
FOCS (Nov 2020).pdfOn Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds
with Lijie Chen, Ron Rothblum, and Eylon Yogev
FOCS 2020; JACM 2023
RANDOM (Aug 2020).pdfOn Hitting-Set Generators for Polynomials that Vanish Rarely
On Hitting-Set Generators for Polynomials that Vanish Rarely
with Dean Doron and Amnon Ta-Shma
RANDOM 2020; Computational Complexity 2022
[ECCC, Sep 2019], [RANDOM, Aug 2020], [Video at RANDOM, Aug 2020]
STOC (Jun 2019).pdfBootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds
Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds
with Lijie Chen
STOC 2019 (best student paper award)
ITCS (Jan 2019).pdfExpander-Based Cryptography Meets Natural Proofs
Expander-Based Cryptography Meets Natural Proofs
with Igor Oliveira and Rahul Santhanam
ITCS 2019; Computational Complexity 2022
TAU (May 2018).pdfProving that prBPP=prP is as hard as proving that "almost NP" is not in P/poly
Proving that prBPP=prP is as hard as proving that "almost NP" is not in P/poly
Information Processing Letters 2019
A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization
A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization
STOC (Jun 2018).pdfQuantified Derandomization of Linear Threshold Circuits
Quantified Derandomization of Linear Threshold Circuits
STOC 2018
[STOC, Jun 2018], [ECCC, Apr 2018], [arXiv, Nov 2017], [Video at STOC, Jun 2018]
CCC (Jul 2017).pdfImproved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials
CCC 2017; Computational Complexity 2019
STACS (Mar 2018).pdfLower Bounds on Black-Box Reductions of Hitting to Density Estimation
Lower Bounds on Black-Box Reductions of Hitting to Density Estimation
STACS 2018
A Note on Tolerant Testing with One-Sided Error
A Note on Tolerant Testing with One-Sided Error
Included in: Computational Complexity and Property Testing
ITCS (Jan 2016).pdfOn Being Far from Far, and on Dual Problems in Property Testing
On Being Far from Far, and on Dual Problems in Property Testing
ITCS 2016
[ECCC, Oct 2017], [ITCS, Jan 2016]
A far-from-far game (Dec 2015) !
An Alternative Proof of an Ω(k) Lower Bound for Testing k-linear Boolean Functions
An Alternative Proof of an Ω(k) Lower Bound for Testing k-linear Boolean Functions
Property Testing Lower Bounds via a Generalization of Randomized Parity Decision Trees
Property Testing Lower Bounds via a Generalization of Randomized Parity Decision Trees
Theory of Computing Systems 2018
Leveraging Memory Mirroring for Transparent Memory Scale-Out with Zero-Downtime Failover of Remote Hosts
Leveraging Memory Mirroring for Transparent Memory Scale-Out with Zero-Downtime Failover of Remote Hosts
with Peter Izsak, Aidan Shribman, Steve Walsh, and Benoit Hudzia
ISCC 2013
(* Operating systems research, done as an undergrad in SAP Research.)
PhD and MSc Theses
PhD and MSc Theses
The two theses below are essentially compilations of research works that I published throughout the corresponding periods of my studies; all the research works included in the theses also appear individually above. As is customary, the theses try to present the included works within some unifying perspective or narrative that is constructed in retrospect.
2020.04.23 phd thesis.pdfDerandomization, Quantified Derandomization, and their Interplay with Lower Bounds
Derandomization, Quantified Derandomization, and their Interplay with Lower Bounds
PhD Thesis
Advisor: Prof. Oded Goldreich
Submitted to the Weizmann Institute of Science, April 2020
2020.04.23 phd defense.pdfHigh-level presentation of the PhD thesis
High-level presentation of the PhD thesis
Presented during the defense of the PhD
Shorter than the 295-page thesis, and has pictures
2015.08.20 msc thesis.pdfDual Problems in Property Testing
Dual Problems in Property Testing
MSc Thesis
Advisor: Prof. Oded Goldreich
Submitted to the Weizmann Institute of Science, August 2015
Google Sites
Report abuse