publications and preprints
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.
2024.04.18 Simons DPT.pdfOpening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL
with Dean Doron and Ted Pyne
STOC 2024
PDFs: ECCC (December 2023)
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization
with Lijie Chen and Ryan Williams
FOCS 2023
PDFs: ECCC (July 2023)
FOCS (Nov 2022).pdfUnstructured Hardness to Average-Case Randomness
with Lijie Chen and Ron Rothblum
FOCS 2022
PDFs: ECCC (July 2022).
2023.06.08 stoc hhtt.pdfDepth-d Threshold Circuits vs Depth-(d+1) AND-OR Trees
with William Hoza, Pooya Hatami, and Avishay Tal
STOC 2023
PDFs: ECCC (June 2022).
UK Complexity (July 2022).pdfWhen Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems
with Lijie Chen
STOC 2023
PDFs: ECCC (April 2022).
How to Find Water in the Ocean: A Survey on Quantified Derandomization
Foundations and Trends in TCS 2022
PDFs: ECCC (Aug 2021), FnT (Oct 2022).
H2R (Sep 2021).pdfHardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
with Lijie Chen
FOCS 2021 (invited to the special issue of SICOMP)
PDFs: ECCC (Jun 2021).
Fooling Constant-Depth Threshold Circuits
with William Hoza, Pooya Hatami, and Avishay Tal
FOCS 2021
PDFs: ECCC (Jan 2021).
Harvard (March 2021).pdfSimple and fast derandomization from very hard functions: Eliminating randomness at almost no cost
with Lijie Chen
STOC 2021
PDFs: ECCC (Sep 2020).
FOCS (Nov 2020).pdfOn Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds
with Lijie Chen, Ron Rothblum, and Eylon Yogev
FOCS 2020; JACM 2023
PDFs: ECCC (Nov 2019).
RANDOM (Aug 2020).pdfOn Hitting-Set Generators for Polynomials that Vanish Rarely
with Dean Doron and Amnon Ta-Shma
RANDOM 2020; Computational Complexity 2022
PDFs: ECCC (Sep 2019), RANDOM (Aug 2020).
STOC (Jun 2019).pdfBootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds
with Lijie Chen
STOC 2019 (best student paper award)
PDFs: STOC (Jun 2019), ECCC (Nov 2018).
ITCS (Jan 2019).pdfExpander-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
Information Processing Letters 2019
PDFs: IPL (Aug 2019), ECCC (Nov 2019).
A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization
PDFs: ECCC (Dec 2017).
STOC (Jun 2018).pdfQuantified Derandomization of Linear Threshold Circuits
STOC 2018
CCC (Jul 2017).pdfImproved 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
STACS 2018
PDFs: STACS (Feb 2018), ECCC (Dec 2017).
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
ITCS 2016
PDFs: 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
Available at ECCC (Aug 2014).
Property Testing Lower Bounds via a Generalization of Randomized Parity Decision Trees
Theory of Computing Systems 2018
PDFs: TCS (Jul 2018), ECCC (Sep 2014).
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
PDFs: ISCC (Jul 2013).
(* Operating systems research, done as an undergrad in SAP Research.)
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
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
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
MSc Thesis
Advisor: Prof. Oded Goldreich
Submitted to the Weizmann Institute of Science, August 2015