Research Interests

A central theme in my work is the development of techniques to understand boolean function complexity, and the application of these techniques to a range of areas in theoretical computer science.

My work has been recognized with best paper awards at FOCS, CCC, and SAT.

Publications

• Lifting uniform learners via distributional decomposition
  
  with Guy Blanc, Jane Lange, and Ali Malik.
  STOC 2023
• Certification with an NP oracle
  
  with Guy Blanc, Caleb Koch, Jane Lange, and Carmen Strassle.
  ITCS 2023
  Video of Carmen's talk.
• Superpolynomial lower bounds for decision tree learning and testing
  
  with Caleb Koch and Carmen Strassle.
  SODA 2023
  See also [Bshouty '23].
• Single-pass streaming algorithms for correlation clustering
  
  with Soheil Behnezhad, Moses Charikar, and Weiyun Ma.
  SODA 2023
• Almost 3-approximate correlation clustering in constant rounds
  
  with Soheil Behnezhad, Moses Charikar, and Weiyun Ma.
  FOCS 2022
• A generalization of the satisfiability coding lemma and its applications
  
  with Milan Mossé and Harry Sha.
  SAT 2022

  Best Paper Award at SAT 2022
  Invited to SAT 2022 special issue
  This was Milan and Harry's CURIS project. See also the original paper [Paturi-Pudlák-Zane '97].
• A query-optimal algorithm for finding counterfactuals
  
  with Guy Blanc, Caleb Koch, and Jane Lange.
  ICML 2022
• Popular decision tree algorithms are provably noise tolerant
  
  with Guy Blanc, Jane Lange, and Ali Malik.
  ICML 2022
• On the power of adaptivity in statistical adversaries
  
  with Guy Blanc, Jane Lange, and Ali Malik.
  COLT 2022
• Open problem: Properly learning decision trees in polynomial time?
  
  with Guy Blanc, Jane Lange, and Mingda Qiao.
  COLT 2022
  Open problems track
• The composition complexity of majority
  
  with Victor Lecomte and Prasanna Ramakrishnan.
  CCC 2022
• Reconstructing decision trees
  
  with Guy Blanc and Jane Lange.
  ICALP 2022
  My slides. See our NeurIPS '21 paper for further applications of these techniques in sublinear algorithms.
• The query complexity of certification
  
  with Guy Blanc, Caleb Koch, and Jane Lange.
  STOC 2022
  A new algorithm for finding certificates, analyzed using concepts from threshold phenomena.
  See also [Gupta-Manoj '22] and our ITCS '23 paper with Carmen.
• Provably efficient, succinct, and precise explanations
  
  with Guy Blanc and Jane Lange.
  NeurIPS 2021
  Explaining black boxes with local computation algorithms. See also [Ribeiro-Singh-Guestrin].
• Properly learning decision trees in almost polynomial time
  
  with Guy Blanc, Jane Lange, and Mingda Qiao.
  FOCS 2021
  Invited to FOCS 2021 special issue

  Journal of the ACM, 2022
  Guy's TCS+ talk. My slides giving a combined overview of this paper and [Blanc-Lange-T '20].
  See also our writeup on possible avenues towards a polynomial-time algorithm.
• Sharper bounds on the Fourier concentration of DNFs
  
  with Victor Lecomte.
  FOCS 2021
  A sharpening of Mansour's bound.
• Tradeoffs in small-depth Frege proofs
  
  with Toniann Pitassi and Prasanna Ramakrishnan.
  FOCS 2021
  A new analogy between correlation bounds in circuit complexity and tradeoffs in proof complexity.
  Builds on [Pitassi-Rossman-Servedio-T '16]. See also [Håstad-Risse '22] for a subsequent improvement.
• Decision tree heuristics can fail, even in the smoothed setting
  
  with Guy Blanc, Jane Lange, and Mingda Qiao.
  RANDOM 2021
  Resolves a conjecture of [Brutzkus-Daniely-Malach]. Video and slides for Mingda's talk.
• Deterministic approximate counting of PTFs via a derandomized regularity lemma
  
  with Rocco Servedio.
  RANDOM 2021
  Video of Rocco's talk.
• On the power and limitations of branch and cut
  
  with Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, and Avi Wigderson.
  CCC 2021
  

  Invited to CCC 2021 special issue
  Video of Noah's talk. See also [BFIKPPR] and [Dadush-Tiwari].
• Brief announcement: A randomness-efficient massively parallel algorithm for Connectivity
  
  with Moses Charikar and Weiyun Ma.
  PODC 2021
• Learning stochastic decision trees
  
  with Guy Blanc and Jane Lange.
  ICALP 2021
• Query strategies for priced information, revisited
  
  with Guy Blanc and Jane Lange.
  SODA 2021
  See also the original paper [CFGKRS '02].
• Universal guarantees for decision tree induction via a higher-order splitting criterion
  
  with Guy Blanc, Neha Gupta, and Jane Lange.
  NeurIPS 2020
  Jane's slides for her honors thesis presentation. Videos of Guy's talks at Cornell and MPI+UCLA.
  My slides for a talk on our work on decision tree induction.
• Estimating decision tree learnability with polylogarithmic sample complexity
  
  with Guy Blanc, Neha Gupta, and Jane Lange.
  NeurIPS 2020
  See also [Kong-Valiant '18] and [Blum-Hu '18].
• Provable guarantees for decision tree induction: the agnostic setting
  
  with Guy Blanc and Jane Lange.
  ICML 2020
  Video and slides for Guy and Jane's talk.
• Fooling Gaussian PTFs via local hyperconcentration
  
  with Ryan O’Donnell and Rocco Servedio.
  STOC 2020
  Video and slides for my talk.
  Subsumed by the journal version with Daniel Kane.
• Non-malleability against polynomial tampering
  
  with Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, and Tal Malkin.
  CRYPTO 2020
• Unconditional lower bounds for adaptive massively parallel computation
  
  with Moses Charikar and Weiyun Ma.
  SPAA 2020
• The power of many samples in query complexity
  
  with Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, and Weiyun Ma.
  ICALP 2020
  See also these papers by Ben-David and Blais.
• Top-down induction of decision trees: rigorous guarantees and inherent limitations
  
  with Guy Blanc and Jane Lange.
  ITCS 2020
  Video and slides for Guy and Jane's talk. See also our ICML '20 and NeurIPS '20 papers for further analyses
  of the heuristics used in practice.
  Best Poster Award, CURIS 2019
• Fooling polytopes
  
  with Ryan O'Donnell and Rocco Servedio.
  STOC 2019
  Invited to STOC 2019 special issue

  Journal of the ACM, 2022
  Videos of Rocco's talk and my talks (IAS, Simons Institute). Ryan's slides and my slides.
  Lecture notes for our high-dimensional Littlewood-Offord theorem.
  See also our FOCS '17 paper and [Arunachalam-Yao '22].
• Improved pseudorandom generators from pseudorandom multi-switching lemmas
  
  with Rocco Servedio.
  RANDOM 2019

  Invited to RANDOM 2019 special issue
• Pseudorandomness for read-k DNF formulas
  
  with Rocco Servedio.
  SODA 2019
• Non-malleable codes for small-depth circuits
  
  with Marshall Ball, Dana Dachman-Soled, Siyao Guo, and Tal Malkin.
  FOCS 2018
• Luby–Veličković–Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
  
  with Rocco Servedio.
  RANDOM 2018
• Deterministic search for CNF satisfying assignments in almost polynomial time
  
  with Rocco Servedio.
  FOCS 2017
• Fooling intersections of low-weight halfspaces
  
  with Rocco Servedio.
  FOCS 2017
  See also [O'Donnell-Servedio-T '19], in which we handle the case of general halfspaces.
• Settling the query complexity of non-adaptive junta testing
  
  with Xi Chen, Rocco Servedio, Erik Waingarten, and Jinyu Xie.
  CCC 2017
  Journal of the ACM, 2018

  Best Paper Award at CCC 2017
  Invited to the Journal of the ACM
  Video of Erik's TCS+ talk. See also [Servedio-T-Wright '15] for an earlier lower bound.
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
  
  with Xi Chen, Rocco Servedio, and Erik Waingarten.
  RANDOM 2017
• What circuit classes can be learned with non-trivial savings?
  
  with Rocco Servedio.
  ITCS 2017
• An average-case depth hierarchy theorem for Boolean circuits
  
  with Johan Håstad, Benjamin Rossman, and Rocco Servedio.
  

  Journal of the ACM, 2017
  Combined journal version of [Rossman-Servedio-T '15] below and [Håstad '16].
• Poly-logarithmic Frege depth lower bounds via an expander switching lemma
  
  with Toniann Pitassi, Benjamin Rossman, and Rocco Servedio.
  STOC 2016
  

  Invited to STOC 2016 special issue
  Slides for my talk. Ryan O'Donnell's lecture on our switching lemma and Sasha Razborov’s discussion of it.
  See also [Håstad '17, Pitassi-Ramakrishnan-T '21, Håstad-Risse '22] for subsequent improvements.
• Near-optimal small-depth lower bounds for small distance connectivity
  
  with Xi Chen, Igor Oliveira, and Rocco Servedio.
  STOC 2016
• Convergence, unanimity, and disagreement in majority dynamics on unimodular graphs and random graphs
  
  with Itai Benjamini, Siu On Chan, Ryan O'Donnell, and Omer Tamuz.
  Stochastic Processes and their Applications, 2016
• Algorithmic signaling of features in auction design
  
  with Shaddin Dughmi, Nicole Immorlica, and Ryan O'Donnell.
  SAGT 2015
• The Polynomial Hierarchy, Random Oracles, and Boolean Circuits
  
  with Benjamin Rossman and Rocco Servedio.
  ACM SIGACT News, December 2015 issue
  
  An overview of [Rossman-Servedio-T '15], with an emphasis on the connections to structural complexity theory.
• An average-case depth hierarchy theorem for Boolean circuits
  
  with Benjamin Rossman and Rocco Servedio.
  FOCS 2015
  

  Best Paper Award at FOCS 2015
  Invited to the Journal of the ACM
  See Computational Complexity, Shtetl-Optimized, Gödel's Lost Letter and P=NP, Combinatorics and more for discussions of our results. See also Boaz Barak's lecture notes, Srikanth Srinivasan's survey, a Simons Institute research vignette, our article in SIGACT News, and my talks at IAS, TCS+, and MSR.
  
• Learning circuits with few negations
  
  with Eric Blais, Clément Canonne, Igor Oliveira, and Rocco Servedio.
  RANDOM 2015
• Adaptivity helps for testing juntas
  
  with Rocco Servedio and John Wright.
  CCC 2015
  See also [Chen-Servedio-T-Waingarten-Xie '17] for an improved lower bound.
• Boolean monotonicity testing requires (almost) n^1/2 non-adaptive queries
  
  with Xi Chen, Anindya De, and Rocco Servedio.
  STOC 2015
  See [Khot-Minzer-Safra '15] for the matching upper bound and [Belovs-Blais '16, Chen-Waingarten-Xie '17] for adaptive lower bounds.
  See our FOCS '14 paper for a simpler proof of a weaker lower bound.
• Approximate resilience, monotonicity, and the complexity of agnostic learning
  
  with Dana Dachman-Soled, Vitaly Feldman, Andrew Wan, and Karl Wimmer.
  SODA 2015
• New algorithms and lower bounds for monotonicity testing
  
  with Xi Chen and Rocco Servedio.
  FOCS 2014
  Videos of talks at IAS and FOCS, and scribe notes on the lower bound.
  See also [Chen-De-Servedio-T '15] for a subsequent improvement of the lower bound.
• On DNF approximators for monotone Boolean functions
  
  with Eric Blais, Johan Håstad, and Rocco Servedio.
  ICALP 2014
• A composition theorem for parity kill number
  
  with Ryan O'Donnell, Xiaorui Sun, John Wright, and Yu Zhao.
  CCC 2014
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
  
  with Manuel Kauers, Ryan O'Donnell, and Yuan Zhou.
  SODA 2014
  Discrete Analysis, 2016
• Learning sums of independent integer random variables
  
  with Costis Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, and Rocco Servedio.
  FOCS 2013
  Invited to Algorithmica Special Issue on Machine Learning.
  Video of my talk at FOCS, and a recap at the MIT Theory student blog.
• On the average sensitivity and density of k-CNF formulas
  
  with Dominik Scheder.
  RANDOM 2013
• A composition theorem for the Fourier Entropy-Influence conjecture
  
  with Ryan O'Donnell.
  ICALP 2013
  
  See also [Wan-Wright-Wu '14] for a new proof of our composition theorem.
• Approximating Boolean functions with depth-2 circuits
  
  with Eric Blais.
  CCC 2013
  SIAM Journal on Computing, 2015
  See also Gödel's Lost Letter and P=NP for a discussion of this paper, and [Blais-Håstad-Servedio-T '14] for related results.
  A video of my talk at the Simons Institute.
• Hypercontractivity via the entropy method
  
  with Eric Blais.
  Theory of Computing, 2013
  Special issue on Analysis of Boolean Functions. 
• New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
  
  with Per Austrin, Ryan O'Donnell, and John Wright.
  ACM Transactions on Computation Theory, 2014
• Attribute-efficient learning and weight-degree tradeoffs for PTFs
  
  with Rocco Servedio and Justin Thaler.
  COLT 2012
• Noise stable halfspaces are close to very small juntas
  
  with Ilias Diakonikolas, Ragesh Jaiswal, Rocco Servedio, and Andrew Wan.
  Chicago Journal of Theoretical Computer Science, 2015
• Bounding the average sensitivity and noise sensitivity of PTFs
  
  with Ilias Diakonikolas, Prasad Raghavendra, and Rocco Servedio.
  STOC 2010
  SIAM Journal on Computing, 2014
  Conference version merged with [Harsha-Klivans-Meka].
• A regularity lemma and low-weight approximators for low-degree PTFs
  
  with Ilias Diakonikolas, Rocco Servedio, and Andrew Wan.
  CCC 2010
  Theory of Computing, 2014