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.
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.
One-way functions and a conditional variant of MKTP. Eric Allender,
Mahdi Cheraghchi,
Dimitrios Myrisiotis,
Harsha Tirumala,
Ilya Volkovich.
FSTTCS 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.
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.
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.
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.