Publications

2024

• Are there graphs whose shortest path structure requires large edge weights? [arXiv]
  Aaron Bernstein, Greg Bodwin, Nicole Wein.
  ITCS 2024.
• New lower bounds in Merlin-Arthur communication and graph streaming verification. [arXiv]
  Prantar Ghosh, Vihan Shah.
  ITCS 2024.
• Oracle efficient online multicalibration and omniprediction. [arXiv]
  Sumegha Garg, Christopher Jung, Omer Reingold, Aaron Roth.
  SODA 2024.
• On approximability of Steiner tree in ℓp-metrics. [arXiv]
  Henry L. Fleischmann, Surya Teja Gavva, Karthik C. S..
  SODA 2024.
• Set covering with our eyes wide shut. [arXiv]
  Anupam Gupta, Gregory Kehne, Roie Levin.
  SODA 2024.
• A unifying framework for differentially private sums under continual observation. [arXiv]
  Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay.
  SODA 2024.
• Optimal bounds on private graph approximation. [arXiv]
  Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou.
  SODA 2024.
• A simple (1 - \varepsilon)-approximation semi-streaming algorithm for maximum (weighted) matching.
  Sepehr Assadi.
  SOSA 2024.
• Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof.
  Karthik C. S., Dániel Marx, Marcin Pilipczuk, Uéverton S. Souza.
  SOSA 2024.

2023

• On constructing spanners from random gaussian projections. [arXiv]
  Sepehr Assadi, Michael Kapralov, Huacheng Yu.
  APPROX/RANDOM 2023.
• Evaluating stability in massive social networks: Efficient streaming algorithms for structural balance. [arXiv]
  Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, Chen Wang.
  APPROX/RANDOM 2023.
• On complexity of 1-Center in various metrics.
  Amir Abboud, MohammadHossein Bateni, Vincent Cohen-Addad, Karthik C. S., Saeed Seddighin.
  APPROX/RANDOM 2023.
• Robustness for space-bounded statistical zero knowledge.
  Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang.
  APPROX/RANDOM 2023.
• Universality of Langevin diffusion for private optimization, with applications to sampling from Rashomon sets.
  Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay.
  COLT 2023.
• Fine-grained buy-many mechanisms are not much better than bundling. [arXiv]
  Sepehr Assadi, Vikram Kher, George Li, Ariel Schvartzman.
  EC 2023.
• Can you solve closest string faster than exhaustive search? [arXiv]
  Amir Abboud, Nick Fischer, Elazar Goldenberg, Karthik C. S., Ron Safier.
  ESA 2023.
• Efficient 1-Laplacian solvers for well-shaped simplicial complexes: Beyond Betti numbers and collapsing sequences.
  Ming Ding, Peng Zhang.
  ESA 2023.
• Hidden permutations to the rescue: Multi-pass streaming lower bounds for approximate matchings.
  Sepehr Assadi, Janani Sundaresan.
  FOCS 2023.
• Generalizing Greenwald-Khanna streaming quantile summaries for weighted inputs. [arXiv]
  Sepehr Assadi, Nirmit Joshi, Milind Prabhu, Vihan Shah.
  ICDT 2023.
• Constant matters: Fine-grained error bound on differentially private continual observation.
  Hendrik Fichtenberger, Monika Henzinger, Jalaj Upadhyay.
  ICML 2023.
• Optimal randomized multilevel Monte Carlo for repeatedly nested expectations. [arXiv]
  Yasa Syed, Guanyang Wang.
  ICML 2023.
• All-norm load balancing in graph streams via the Multiplicative Weights Update method. [arXiv]
  Sepehr Assadi, Aaron Bernstein, Zachary Langley.
  ITCS 2023.
• Kolmogorov complexity characterizes statistical zero knowledge.
  Eric Allender, Shuichi Hirahara, Harsha Tirumala.
  ITCS 2023.
• Coloring in graph streams via deterministic and adversarially robust algorithms. [arXiv]
  Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl.
  PODS 2023.
• Optimal uncoordinated unique IDs. [arXiv]
  Peter C. Dillinger, Martin Farach-Colton, Guido Tagliavini, Stefan Walzer.
  PODS 2023.
• Tight bounds for monotone minimal perfect hashing. [arXiv]
  Sepehr Assadi, Martin Farach-Colton, William Kuszmaul.
  SODA 2023.
• Closing the gap between directed hopsets and shortcut sets. [arXiv]
  Aaron Bernstein, Nicole Wein.
  SODA 2023.
• Tiny pointers. [arXiv]
  Michael A. Bender, Alex Conway, Martin Farach-Colton, William Kuszmaul, Guido Tagliavini.
  SODA 2023.
• Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.
  Michal Koucký, Michael E. Saks.
  SODA 2023.
• Almost tight error bounds on differentially private continual counting. [arXiv]
  Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay.
  SODA 2023.
• Tight bounds for vertex connectivity in dynamic streams. [arXiv]
  Sepehr Assadi, Vihan Shah.
  SOSA 2023.
• A tight analysis of Hutchinson's diagonal estimator. [arXiv]
  Prathamesh Dharangutte, Christopher Musco.
  SOSA 2023.
• An associativity threshold phenomenon in set-associative caches. [arXiv]
  Michael A. Bender, Rathish Das, Martin Farach-Colton, Guido Tagliavini.
  SPAA 2023.
• On regularity lemma and barriers in streaming and dynamic matching. [arXiv]
  Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li.
  STOC 2023.
• (Noisy) Gap Cycle Counting strikes back: Random order streaming lower bounds For connected components and beyond. [arXiv]
  Sepehr Assadi, Janani Sundaresan.
  STOC 2023.

2022

• Asymptotically optimal bounds for estimating h-index in sublinear time with applications to subgraph counting.
  Sepehr Assadi, Hoai-An Nguyen.
  APPROX/RANDOM 2022.
• Learning generalized depth three arithmetic circuits in the non-degenerate case.
  Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha.
  APPROX/RANDOM 2022.
• Space Optimal Vertex Cover in Dynamic Streams. [arXiv]
  Kheeran K. Naidu, Vihan Shah.
  APPROX/RANDOM 2022.
• Almost polynomial factor inapproximability for parameterized k-clique.
  Karthik C. S., Subhash Khot.
  CCC 2022.
• On Randomized Reductions to the Random Strings.
  Michael E. Saks, Rahul Santhanam.
  CCC 2022.
• Hierarchical clustering in graph streams: Single-pass algorithms and space lower bounds. [arXiv]
  Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki, Vahab Mirrokni, Chen Wang.
  COLT 2022.
• Graph coloring, palette sparsification, and beyond (Invited Talk).
  Sepehr Assadi.
  DISC 2022.
• Rounds vs Communication Tradeoffs for Maximal Independent Sets. [arXiv]
  Sepehr Assadi, Gillat Kol, Zhijun Zhang.
  FOCS 2022.
• Negative-Weight Single-Source Shortest Paths in Near-linear Time. [arXiv]
  Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen.
  FOCS 2022.
• Online List Labeling: Breaking the log
  Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein.
  FOCS 2022.
• Fast Multivariate Multipoint Evaluation Over All Finite Fields. [arXiv]
  Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans.
  FOCS 2022.
• Decremental matching in general graphs. [arXiv]
  Sepehr Assadi, Aaron Bernstein, Aditi Dudeja.
  ICALP 2022.
• Fully-dynamic graph sparsifiers against an adaptive adversary. [arXiv]
  Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun.
  ICALP 2022.
• Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. [arXiv]
  Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang.
  ICALP 2022.
• Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. [arXiv]
  Ming Ding, Rasmus Kyng, Peng Zhang.
  ICALP 2022.
• An asymptotically optimal algorithm for maximum matching in dynamic streams. [arXiv]
  Sepehr Assadi, Vihan Shah.
  ITCS 2022.
• Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions. [arXiv]
  Sepehr Assadi, Chen Wang.
  ITCS 2022.
• What does dynamic optimality mean in external memory? [arXiv]
  Michael A. Bender, Martin Farach-Colton, William Kuszmaul.
  ITCS 2022.
• Obtaining Approximately Optimal and Diverse Solutions via Dispersion. [arXiv]
  Jie Gao, Mayank Goswami, Karthik C. S., Meng-Tsung Tsai, Shih-Yu Tsai, Hao-Tsung Yang.
  LATIN 2022.
• Semi-streaming bipartite matching in fewer passes and optimal space. [arXiv]
  Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian.
  SODA 2022.
• A two-pass (conditional) lower bound for semi-streaming maximum matching.
  Sepehr Assadi.
  SODA 2022.
• Co-evolution of opinion and social tie dynamics towards structural balance. [arXiv]
  Haotian Wang, Feng Luo, Jie Gao.
  SODA 2022.
• Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics. [arXiv]
  Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee.
  SODA 2022.
• Brooks' theorem in graph streams: A single-pass semi-streaming algorithm for Δ-coloring.
  Sepehr Assadi, Pankaj Kumar, Parth Mittal.
  STOC 2022.
• Deterministic graph coloring in the streaming model. [arXiv]
  Sepehr Assadi, Andrew Chen, Glenn Sun.
  STOC 2022.
• On the optimal time/space tradeoff for hash tables. [arXiv]
  Michael A. Bender, Martin Farach-Colton, John Kuszmaul, William Kuszmaul, Mingmou Liu.
  STOC 2022.
• Fast, algebraic multivariate multipoint evaluation in small characteristic and applications. [arXiv]
  Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, Chandra Kanta Mohapatra.
  STOC 2022.

2021

• Adversarially robust low dimensional representations. [arXiv]
  Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan.
  COLT 2021.
• Ruling sets in random order and adversarial streams.
  Sepehr Assadi, Aditi Dudeja.
  DISC 2021.
• Designing a combinatorial financial options market.
  Xintong Wang, David M. Pennock, Nikhil R. Devanur, David M. Rothschild, Biaoshuai Tao, Michael P. Wellman.
  EC 2021.
• Graph connectivity and single element recovery via linear and OR queries. [arXiv]
  Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna.
  ESA 2021.
• Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach. [arXiv]
  Sepehr Assadi, Shay Solomon.
  ESA 2021.
• Incremental SCC maintenance in sparse graphs.
  Aaron Bernstein, Aditi Dudeja, Seth Pettie.
  ESA 2021.
• Deterministic decremental SSSP and approximate min-cost flow in almost-linear time. [arXiv]
  Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak.
  FOCS 2021.
• Applications of random algebraic constructions to hardness of approximation. [arXiv]
  Boris Bukh, Karthik C. S., Bhargav Narayanan.
  FOCS 2021.
• One-way functions and a conditional variant of MKTP.
  Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich.
  FSTTCS 2021.
• Beating two-thirds for random-order streaming matching. [arXiv]
  Sepehr Assadi, Soheil Behnezhad.
  ICALP 2021.
• A Framework for Private Matrix Analysis in Sliding Window Model.
  Jalaj Upadhyay, Sarvagya Upadhyay.
  ICML 2021.
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity.
  Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle.
  ISAAC 2021.
• Depth-first search in directed planar graphs, revisited.
  Eric Allender, Archit Chauhan, Samir Datta.
  MFCS 2021.
• Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. [arXiv]
  Sepehr Assadi, Thomas Kesselheim, Sahil Singla.
  SODA 2021.
• Beating greedy for approximating reserve prices in multi-unit VCG auctions. [arXiv]
  Mahsa Derakhshan, David M. Pennock, Aleksandrs Slivkins.
  SODA 2021.
• Deterministic replacement path covering. [arXiv]
  Karthik C. S., Merav Parter.
  SODA 2021.
• On approximability of clustering problems without candidate centers. [arXiv]
  Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee.
  SODA 2021.
• An auction algorithm for bipartite matching in streaming and massively parallel computation models.
  Sepehr Assadi, S. Cliff Liu, Robert E. Tarjan.
  SOSA 2021.
• A simple semi-streaming algorithm for global minimum cuts.
  Sepehr Assadi, Aditi Dudeja.
  SOSA 2021.
• On hardness of approximation of parameterized set cover and label cover: Threshold graphs from error correcting codes. [arXiv]
  Karthik C. S., Inbal Livni Navon.
  SOSA 2021.
• Paging and the address-translation problem.
  Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martin Farach-Colton, Rob Johnson, Sudarsun Kannan, William Kuszmaul, Nirjhar Mukherjee, Donald E. Porter, Guido Tagliavini, Janet Vorobyeva, Evan West.
  SPAA 2021.
• Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma. [arXiv]
  Sepehr Assadi, Vishvajeet N.
  STOC 2021.
• A framework for dynamic matching in weighted graphs.
  Aaron Bernstein, Aditi Dudeja, Zachary Langley.
  STOC 2021.
• Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits.
  Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich.
  STOC 2021.

2020

• Geometric rank of tensors and subrank of matrix multiplication. [arXiv]
  Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam.
  CCC 2020.
• Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions.
  Michael E. Saks, Rahul Santhanam.
  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 AC0[⊕] 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 (Δ+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 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.
• On the Complexity of Sampling Vertices Uniformly from a Graph.
  Flavio Chierichetti, Shahrzad Haddadan.
  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 ˜O(m√n) expected total time. [pdf]
  Aaron Bernstein, Shiri Chechik.
  SODA 2018.
• Online bipartite matching with O(log2n) 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 Z/2kZ∗.
  Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan.
  STACS 2017.
• Algorithmic information, plane Kakeya sets, and conditional dimension. [arXiv]
  Jack H. Lutz, Neil Lutz.
  STACS 2017.
• Mixing of Permutations by Biased Transposition.
  Shahrzad Haddadan, Peter Winkler.
  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 W. 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.