Below is a list of recent publications by Rutgers students and faculty members
in theory conferences. To see a list of publications beyond just theory
conferences, click here. Rutgers members' names are
underlined in the author lists.
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.
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.
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.
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.
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.
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 $\ell_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 $\Delta$-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.
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.
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.
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 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.
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.
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.
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.
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.
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.
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.
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.