Publications
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
Preliminary version in FOCS 2023.
Lifting with Inner Functions of Polynomial Discrepancy
with Yahel Manor.
Preliminary version in RANDOM 2022.
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0
with Yuval Filmus and Avishay Tal.
Accepted to Theory of Computing.
Preliminary version in ITCS 2021.
KRW Composition Theorems via Lifting
with Susanna de-Rezenda, Jakob Nordström, Toniann Pitassi, and Robert Robere.
Accepted to Computational Complexity.
Preliminary version in FOCS 2020.
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
with Susanna de-Rezenda, Jakob Nordström, and Robert Robere.
Computational Complexity, 30(1), 2021.
Preliminary version in CCC 2019.
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
with Susanna de-Rezenda, Jakob Nordström, Toniann Pitassi, Robert Robere, and Marc Vinyals.
Preliminary version in FOCS 2020.
Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation
Computational Complexity, 29(1), 2020.
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
with Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Toniann Pitassi.
SIAM Journal on Computing, 50(1), 2021.
Preliminary version in ICALP 2019 (under the title "Query-To-Communication Lifting for BPP Using Inner Product").
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
with Avi Wigderson.
Computational Complexity, 28(2), 2019.
On Derandomized Composition of Boolean Functions
Computational Complexity, 28(4), 2019.
Improved Composition Theorems for Functions and Relations
with Sajin Koroth.
Preliminary version in RANDOM 2018.
The Choice and Agreement Problems of a Random Function
with Avishay Tal.
Information Processing Letters, 133, 2018.
An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds
The Direct Sum of Universal Relations
Information Processing Letters, 136, 2018.
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
with Irit Dinur.
Computational Complexity, 27(3), 2018.
Preliminary version in CCC 2016.
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
with Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf.
Journal of the ACM, 64(2), 2017.
Preliminary version in STOC 2016.
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
with Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, and Henning Stichtenoth.
Journal of the ACM, 63(4), 2016.
Preliminary version in FOCS 2013.
with Dmitry Gavinsky, Omri Weinstein, and Avi Wigderson.
Preliminary version in STOC 2014.
SIAM Journal on Computing, 46(1), 2017 (under the title "Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation").
Combinatorial PCPs with Short Proofs
Preliminary version in CCC 2012.
Computational Complexity, 25(1), 2016.
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly
with Oded Goldreich.
ACM Transcations on Computation Theory (ToCT), 7(4), 2015.
Derandomized Parallel Repetition via Structured PCPs
with Irit Dinur.
Computational Complexity 20(2), 2011 (invited paper).
Preliminary version in CCC 2010.
IP = PSPACE using Error Correcting Codes
SIAM Journal on Computing (SICOMP), 42(1), 2013.
Combinatorial PCPs with Efficient Verifiers
Computational Complexity 23(3), 2014.
Preliminary version in FOCS 2009.
Combinatorial Construction of Locally Testable Codes
SIAM Journal on Computing (SICOMP), 39(2), 2009.
Preliminary version in STOC 2008.
On the Efficiency of Non-Uniform PCPP Verifiers
On the Rectangle Method in proofs of Robustness of Tensor Products
Information Processing Letters, 112(6), 2012.
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable
with Oded Goldreich.
Information Processing Letters, 112(8-9), 2012.