Publications

2020

• Palette sparsification beyond $(\Delta + 1)$ vertex coloring. [arXiv]
  Noga Alon, Sepehr Assadi.
  APPROX/RANDOM 2020.
• On multilinear forms: Bias, correlation, and tensor rank. [arXiv]
  Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar.
  APPROX/RANDOM 2020.
• On the list recoverability of randomly punctured codes. [arXiv]
  Ben D. Lund, Aditya Potukuchi.
  APPROX/RANDOM 2020.
• Geometric rank of tensors and subrank of matrix multiplication. [arXiv]
  Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam.
  CCC 2020.
• Estimating principal components under adversarial perturbations. [arXiv]
  Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan.
  COLT 2020.
• Indifferentiability for public key cryptosystems.
  Mark Zhandry, Cong Zhang.
  CRYPTO 2020.
• Improved bounds for distributed load balancing. [arXiv]
  Sepehr Assadi, Aaron Bernstein, Zachary Langley.
  DISC 2020.
• Cutting polygons into small pieces with chords: Laser-based localization. [arXiv]
  Esther M. Arkin, Rathish Das, Jie Gao, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk, Csaba D. Tóth.
  ESA 2020.
• Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms. [arXiv]
  Sepehr Assadi, Ran Raz.
  FOCS 2020.
• Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. [arXiv]
  Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu.
  FOCS 2020.
• Near-Optimal Decremental SSSP in Dense Weighted Digraphs. [arXiv]
  Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen.
  FOCS 2020.
• Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. [arXiv]
  Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak.
  FOCS 2020.
• Proximity Gaps for Reed-Solomon Codes.
  Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf.
  FOCS 2020.
• Online matching with recourse: Random edge arrivals.
  Aaron Bernstein, Aditi Dudeja.
  FSTTCS 2020.
• Improved bounds for matching in random-order streams. [arXiv]
  Aaron Bernstein.
  ICALP 2020.
• A spectral bound on hypergraph discrepancy. [arXiv]
  Aditya Potukuchi.
  ICALP 2020.
• Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks. [arXiv]
  Pranjal Awasthi, Natalie Frank, Mehryar Mohri.
  ICML 2020.
• No-Regret and Incentive-Compatible Online Learning. [arXiv]
  Rupert Freeman, David M. Pennock, Chara Podimata, Jennifer Wortman Vaughan.
  ICML 2020.
• DEEP-FRI: Sampling outside the box improves soundness. [arXiv]
  Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf.
  ITCS 2020.
• Lower bounds for distributed sketching of maximal matchings and maximal independent sets.
  Sepehr Assadi, Gillat Kol, Rotem Oshman.
  PODC 2020.
• Flushing without cascades. [pdf]
  Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, William Kuszmaul.
  SODA 2020.
• Reconstruction of depth-4 multilinear circuits. [eccc]
  Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich.
  SODA 2020.
• Improved inapproximability of rainbow coloring. [arXiv]
  Per Austrin, Amey Bhangale, Aditya Potukuchi.
  SODA 2020.
• Streaming complexity of spanning tree computation. [arXiv]
  Yi-Jun Chang, Martin Farach-Colton, Tsan-sheng Hsu, Meng-Tsung Tsai.
  STACS 2020.
• Separating the communication complexity of truthful and non-truthful combinatorial auctions.
  Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg.
  STOC 2020.
• Exploration with limited memory: streaming algorithms for coin tossing, noisy comparisons, and multi-armed bandits. [arXiv]
  Sepehr Assadi, Chen Wang.
  STOC 2020.
• Constant factor approximations to edit distance on far input pairs in nearly linear time. [arXiv]
  Michal Koucký, Michael E. Saks.
  STOC 2020.

2019

• Bilu-Linial stability, certified algorithms and the independent set problem. [arXiv]
  Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, Chen Dan.
  ESA 2019.
• Improved truthful mechanisms for combinatorial auctions with submodular bidders. [arXiv]
  Sepehr Assadi, Sahil Singla.
  FOCS 2019.
• Quasilinear time list-decodable codes for space bounded channels. [eccc]
  Jad Silbak, Swastik Kopparty, Ronen Shaltiel.
  FOCS 2019.
• Towards a theory of non-commutative optimization: geodesic 1st and 2nd order methods for moment maps and polytopes. [arXiv]
  Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson.
  FOCS 2019.
• On the $\text{AC}^0[\oplus]$ complexity of Andreev's problem. [arXiv]
  Aditya Potukuchi.
  FSTTCS 2019.
• When algorithms for maximal independent set and maximal matching run in sublinear time. [pdf]
  Sepehr Assadi, Shay Solomon.
  ICALP 2019.
• Robust communication-optimal distributed clustering algorithms. [arXiv]
  Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff.
  ICALP 2019.
• Distributed weighted matching via randomized composable coresets. [arXiv]
  Sepehr Assadi, MohammadHossein Bateni, Vahab S. Mirrokni.
  ICML 2019.
• Fair $k$-center clustering for data summarization. [arXiv]
  Matthäus Kleindessner, Pranjal Awasthi, Jamie Morgenstern.
  ICML 2019.
• Guarantees for spectral clustering with fairness constraints. [arXiv]
  Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, Jamie Morgenstern.
  ICML 2019.
• A simple sublinear-time algorithm for counting arbitrary subgraphs via edge sampling. [arXiv]
  Sepehr Assadi, Michael Kapralov, Sanjeev Khanna.
  ITCS 2019.
• Torus polynomials: an algebraic approach to ACC lower bounds. [arXiv]
  Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao.
  ITCS 2019.
• Massively parallel algorithms for finding well-connected components in sparse graphs. [arXiv]
  Sepehr Assadi, Xiaorui Sun, Omri Weinstein.
  PODC 2019.
• Distributed and streaming linear programming in low dimensions. [arXiv]
  Sepehr Assadi, Nikolai Karpov, Qin Zhang.
  PODS 2019.
• Stochastic submodular cover with limited adaptivity. [arXiv]
  Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna.
  SODA 2019.
• Sublinear algorithms for $(\Delta + 1)$ vertex coloring. [arXiv]
  Sepehr Assadi, Yu Chen, Sanjeev Khanna.
  SODA 2019.
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. [arXiv]
  Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, Cliff Stein.
  SODA 2019.
• Fully dynamic maximal independent set with sublinear in $n$ update time. [arXiv]
  Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon.
  SODA 2019.
• A deamortization approach for dynamic spanner and dynamic maximal matching. [arXiv]
  Aaron Bernstein, Sebastian Forster, Monika Henzinger.
  SODA 2019.
• Optimal ball recycling. [arXiv]
  Michael A. Bender, Jake Christensen, Alex Conway, Martin Farach-Colton, Rob Johnson, Meng-Tsung Tsai.
  SODA 2019.
• A deterministic PTAS for the algebraic rank of bounded degree polynomials. [pdf]
  Vishwas Bhargava, Markus Bläser, Gorav Jindal, Anurag Pandey.
  SODA 2019.
• Towards a unified theory of sparsification for matching problems. [arXiv]
  Sepehr Assadi, Aaron Bernstein.
  SOSA@SODA 2019.
• Small refinements to the DAM can have big consequences for data-structure design.
  Michael A. Bender, Alex Conway, Martin Farach-Colton, William Jannen, Yizheng Jiao, Rob Johnson, Eric Knorr, Sara McAllister, Nirjhar Mukherjee, Prashant Pandey, Donald E. Porter, Jun Yuan, Yang Zhan.
  SPAA 2019.
• Polynomial pass lower bounds for graph streaming algorithms. [arXiv]
  Sepehr Assadi, Yu Chen, Sanjeev Khanna.
  STOC 2019.
• Distributed exact weighted all-pairs shortest paths in near-linear time. [arXiv]
  Aaron Bernstein, Danupon Nanongkai.
  STOC 2019.
• Decremental strongly-connected components and single-source reachability in near-linear time. [arXiv]
  Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen.
  STOC 2019.
• Achieving optimal backlog in multi-processor cup games. [arXiv]
  Michael A. Bender, Martin Farach-Colton, William Kuszmaul.
  STOC 2019.

2018

• Worst-case to average case reductions for the distance to a code.
  Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf.
  CCC 2018.
• Towards learning sparsely used dictionaries with arbitrary supports. [arXiv]
  Pranjal Awasthi, Aravindan Vijayaraghavan.
  FOCS 2018.
• Bloom filters, adaptivity, and the dictionary problem. [arXiv]
  Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, Shikha Singh.
  FOCS 2018.
• Improved decoding of folded reed-solomon and multiplicity codes. [arXiv]
  Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters.
  FOCS 2018.
• Deterministic factorization of sparse polynomials with bounded individual degree. [arXiv]
  Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich.
  FOCS 2018.
• Approximating edit distance within constant factor in truly sub-quadratic time. [arXiv]
  Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks.
  FOCS 2018.
• Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. [arXiv]
  Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson.
  FOCS 2018.
• Optimal hashing in external memory. [arXiv]
  Alexander Conway, Martin Farach-Colton, Philip Shilane.
  ICALP 2018.
• Clustering semi-random mixtures of gaussians. [arXiv]
  Pranjal Awasthi, Aravindan Vijayaraghavan.
  ICML 2018.
• Crowdsourcing with arbitrary adversaries. [pdf]
  Matthäus Kleindessner, Pranjal Awasthi.
  ICML 2018.
• Streaming algorithms for planar convex hulls. [arXiv]
  Martin Farach-Colton, Meng Li, Meng-Tsung Tsai.
  ISAAC 2018.
• Minimum circuit size, graph isomorphism, and related problems. [arXiv]
  Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan.
  ITCS 2018.
• Distance-preserving graph contractions. [arXiv]
  Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny.
  ITCS 2018.
• Incremental topological sort and cycle detection in $\widetilde{O}(m\sqrt{n})$ expected total time. [pdf]
  Aaron Bernstein, Shiri Chechik.
  SODA 2018.
• Online bipartite matching with $O(\log^2{n})$ amortized replacements. [arXiv]
  Aaron Bernstein, Jacob Holm, Eva Rotenberg.
  SODA 2018.
• Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields. [arXiv]
  Swastik Kopparty, Aditya Potukuchi.
  SODA 2018.
• Near-optimal approximation algorithm for simultaneous max-cut. [arXiv]
  Amey Bhangale, Subhash Khot, Swastik Kopparty, Sushant Sachdeva, Devanathan Thiruvenkatachari.
  SODA 2018.
• Lower bounds for combinatorial algorithms for boolean matrix multiplication. [arXiv]
  Debarati Das, Michal Koucký, Michael E. Saks.
  STACS 2018.
• Operator scaling with specified marginals. [arXiv]
  Cole Franks.
  STOC 2018.

2017

• The Moser-Tardos resample algorithm: where is the limit? (An experimental inquiry).
  Jan Dean Catarata, Scott Corbett, Harry Stern, Mario Szegedy, Tomás Vyskocil, Zheng Zhang.
  ALENEX 2017.
• An exponential lower bound for homogeneous depth-5 circuits over finite fields.
  Mrinal Kumar, Ramprasad Saptharishi.
  CCC 2017.
• A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs.
  Mrinal Kumar.
  CCC 2017.
• Efficient PAC learning from the crowd. [arXiv]
  Pranjal Awasthi, Avrim Blum, Nika Haghtalab, Yishay Mansour.
  COLT 2017.
• Breaking the FF3 format-preserving encryption standard over small domains.
  F. Betül Durak, Serge Vaudenay.
  CRYPTO 2017.
• An improved dictatorship test with perfect completeness. [arXiv]
  Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari.
  FSTTCS 2017.
• Cube vs. cube low degree test. [arXiv]
  Amey Bhangale, Irit Dinur, Inbal Livni Navon.
  ITCS 2017.
• Better complexity bounds for cost register automata.
  Eric Allender, Andreas Krebs, Pierre McKenzie.
  MFCS 2017.
• New insights on the (non-)hardness of circuit minimization and related problems.
  Eric Allender, Shuichi Hirahara.
  MFCS 2017.
• Fractal intersections and products via algorithmic dimension. [arXiv]
  Neil Lutz.
  MFCS 2017.
• Stateless computation. [arXiv]
  Danny Dolev, Michael Erdmann, Neil Lutz, Michael Schapira, Adva Zair.
  PODC 2017.
• Write-optimized skip lists.
  Michael A. Bender, Martin Farach-Colton, Rob Johnson, Simon Mauras, Tyler Mayer, Cynthia A. Phillips, Helen Xu.
  PODS 2017.
• Cross-referenced dictionaries and the limits of write optimization.
  Peyman Afshani, Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Mayank Goswami, Meng-Tsung Tsai.
  SODA 2017.
• Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound.
  Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf.
  SODA 2017.
• Maximally recoverable codes for grid-like topologies. [arXiv]
  Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin.
  SODA 2017.
• Accurate and nearly optimal sublinear approximations to Ulam distance.
  Timothy Naumovitz, Michael E. Saks, C. Seshadhri.
  SODA 2017.
• On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}^*$.
  Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan.
  STACS 2017.
• Algorithmic information, plane Kakeya sets, and conditional dimension. [arXiv]
  Jack H. Lutz, Neil Lutz.
  STACS 2017.

2016

• Decoding Reed-Muller codes over product sets. [arXiv]
  John Y. Kim, Swastik Kopparty.
  CCC 2016.
• Arithmetic circuits with locally low algebraic rank. [arXiv]
  Mrinal Kumar, Shubhangi Saraf.
  CCC 2016.
• Sums of products of polynomials in few variables: lower bounds and polynomial identity testing. [arXiv]
  Mrinal Kumar, Shubhangi Saraf.
  CCC 2016.
• Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity. [arXiv]
  Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi.
  CCC 2016.
• Learning and 1-bit compressed sensing under asymmetric noise.
  Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Hongyang Zhang.
  COLT 2016.
• Depth-reduction for composites.
  Shiteng Chen, Periklis A. Papakonstantinou.
  FOCS 2016.
• Noisy population recovery in polynomial time. [arXiv]
  Anindya De, Michael E. Saks, Sijian Tang.
  FOCS 2016.
• Finer separations between shallow arithmetic circuits.
  Mrinal Kumar, Ramprasad Saptharishi.
  FSTTCS 2016.
• Bicovering: covering edges with two small subsets of vertices.
  Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz.
  ICALP 2016.
• On the power and limits of distance-based learning.
  Periklis A. Papakonstantinou, Jia Xu, Guang Yang.
  ICML 2016.
• Spectral embedding of $k$-cliques, graph partitioning and $k$-means.
  Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop.
  ITCS 2016.
• The I/O complexity of computing prime tables.
  Michael A. Bender, Rezaul Chowdhury, Alexander Conway, Martin Farach-Colton, Pramod Ganapathi, Rob Johnson, Samuel McCauley, Bertrand Simon, Shikha Singh.
  LATIN 2016.
• Tight approximations of degeneracy in large graphs.
  Martin Farach-Colton, Meng-Tsung Tsai.
  LATIN 2016.
• Robust positioning patterns.
  Ross Berkowitz, Swastik Kopparty.
  SODA 2016.
• High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. [arXiv]
  Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf.
  STOC 2016.

2015

• A characterization of hard-to-cover CSPs. [arXiv]
  Amey Bhangale, Prahladh Harsha, Girish Varma.
  CCC 2015.
• Simultaneous approximation of constraint satisfaction problems. [arXiv]
  Amey Bhangale, Swastik Kopparty, Sushant Sachdeva.
  ICALP 2015.
• On the complexity of computing prime tables. [arXiv]
  Martin Farach-Colton, Meng-Tsung Tsai.
  ISAAC 2015.
• Exact and FPT algorithms for max-conflict free coloring in hypergraphs.
  Pradeesha Ashok, Aditi Dudeja, Sudeshna Kolay.
  ISAAC 2015.
• A new approach to the sensitivity conjecture.
  Justin Gilmer, Michal Koucký, Michael E. Saks.
  ITCS 2015.
• Dual VP classes.
  Eric Allender, Anna Gál, Ian Mertz.
  MFCS 2015.
• A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity.
  Timothy Naumovitz, Michael E. Saks.
  SODA 2015.
• Cost-oblivious reallocation for scheduling and planning.
  Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert.
  SPAA 2015.
• The minimum oracle circuit size problem.
  Eric Allender, Dhiraj Holden, Valentine Kabanets.
  STACS 2015.

2014

• Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization.
  Swastik Kopparty, Shubhangi Saraf, Amir Shpilka.
  CCC 2014.
• Recent progress on lower bounds for arithmetic circuits.
  Shubhangi Saraf.
  CCC 2014.
• The batched predecessor problem in external memory.
  Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Dzejla Medjedovic, Pablo Montes, Meng-Tsung Tsai.
  ESA 2014.
• On the power of homogeneous depth 4 arithmetic circuits. [arXiv]
  Mrinal Kumar, Shubhangi Saraf.
  FOCS 2014.
• Local tests of global entanglement and a counterexample to the generalized area law. [arXiv]
  Dorit Aharonov, Aram Wettroth Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani.
  FOCS 2014.
• Algorithms, games, and evolution (invited talk).
  Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani.
  FSTTCS 2014.
• Efficient indexing of necklaces and irreducible polynomials over finite fields. [arXiv]
  Swastik Kopparty, Mrinal Kumar, Michael E. Saks.
  ICALP 2014.
• Lower bounds for approximate LDCs. [arXiv]
  Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf.
  ICALP 2014.
• Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. [arXiv]
  Mrinal Kumar, Shubhangi Saraf.
  ICALP 2014.
• Computing the degeneracy of large graphs.
  Martin Farach-Colton, Meng-Tsung Tsai.
  LATIN 2014.
• Helly-type theorems in property testing. [arXiv]
  Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, Shubhangi Saraf.
  LATIN 2014.
• Low-depth uniform threshold circuits and the bit-complexity of straight line programs.
  Eric Allender, Nikhil Balaji, Samir Datta.
  MFCS 2014.
• Zero knowledge and circuit minimization.
  Eric Allender, Bireswar Das.
  MFCS 2014.
• Cost-oblivious storage reallocation. [arXiv]
  Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert.
  PODS 2014.
• Self-stabilizing uncoupled dynamics. [arXiv]
  Aaron D. Jaggard, Neil Lutz, Michael Schapira, Rebecca N. Wright.
  SAGT 2014.
• The limits of depth reduction for arithmetic formulas: it's all about the top fan-in. [arXiv]
  Mrinal Kumar, Shubhangi Saraf.
  STOC 2014.
• Breaking the quadratic barrier for 3-LCC's over the reals.
  Zeev Dvir, Shubhangi Saraf, Avi Wigderson.
  STOC 2014.
• Parallel algorithms for geometric graph problems. [arXiv]
  Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev.
  STOC 2014.