Publications

2022

• Subspace differential privacy. [arXiv]
  Jie Gao, Ruobin Gong, Fang-Yi Yu.
  AAAI 2022.
• A synthetic prediction market for estimating confidence in published work. [arXiv]
  Sarah Michele Rajtmajer, Christopher Griffin, Jian Wu, Robert Fraleigh, Laxmaan Balaji, Anna Cinzia Squicciarini, Anthony Kwasnica, David M. Pennock, Michael McLaughlin, Timothy Fritton, Nishanth Nakshatri, Arjun Manoj Menon, Sai Ajay Modukuri, Rajal Nivargi, Xin Wei, C. Lee Giles.
  AAAI 2022.
• Optimal local bayesian differential privacy over Markov chains. [arXiv]
  Darshan Chakrabarti, Jie Gao, Aditya Saraf, Grant Schoenebeck, Fang-Yi Yu.
  AAMAS 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.
• Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning.
  Teng Guo, Si Wei Feng, Mario Szegedy, Jingjin Yu.
  Allerton 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.
• Budgeted Steiner Networks: Three Terminals with Equal Path Weights. [arXiv]
  Jingjin Yu, Mario Szegedy.
  CCCG 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.
• Publishing asynchronous event times with Pufferfish privacy.
  Jiaxin Ding, Abhirup Ghosh, Rik Sarkar, Jie Gao.
  DCOSS 2022.
• Graph coloring, palette sparsification, and beyond (Invited Talk).
  Sepehr Assadi.
  DISC 2022.
• BetrFS: a compleat file system for commodity SSDs.
  Yizheng Jiao, Simon Bertron, Sagar Patel, Luke Zeller, Rory Bennett, Nirjhar Mukherjee, Michael A. Bender, Michael Condict, Alex Conway, Martin Farach-Colton, Xiongzi Ge, William Jannen, Rob Johnson, Donald E. Porter, Jun Yuan.
  EuroSys 2022.
• ABCinML: Anticipatory bias correction in machine learning applications. [arXiv]
  Abdulaziz A. Almuzaini, Chidansh A. Bhatt, David M. Pennock, Vivek K. Singh.
  FAccT 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.
• 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.
• Spine: Scaling up programming-by-negative-example for string filtering and transformation.
  Chaoji Zuo, Sepehr Assadi, Dong Deng.
  SIGMOD Conference 2022.
• GraphZeppelin: Storage-friendly sketching for connected components on dynamic graph streams. [arXiv]
  David Tench, Evan West, Victor Zhang, Michael A. Bender, Abiyaz Chowdhury, J. Ahmed Dellas, Martin Farach-Colton, Tyler Seip, Kenny Zhang.
  SIGMOD Conference 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.
• On cyclic solutions to the min-max latency multi-robot patrolling problem. [arXiv]
  Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang.
  SoCG 2022.

2021

• Graph learning for inverse landscape genetics. [arXiv]
  Prathamesh Dharangutte, Christopher Musco.
  AAAI 2021.
• Log-time prediction markets for interval securities. [arXiv]
  Miroslav Dudík, Xintong Wang, David M. Pennock, David M. Rothschild.
  AAMAS 2021.
• Measuring model fairness under noisy covariates: A theoretical perspective. [arXiv]
  Flavien Prost, Pranjal Awasthi, Nick Blumm, Aditee Kumthekar, Trevor Potter, Li Wei, Xuezhi Wang, Ed H. Chi, Jilin Chen, Alex Beutel.
  AIES 2021.
• A deep conditioning treatment of neural networks. [arXiv]
  Naman Agarwal, Pranjal Awasthi, Satyen Kale.
  ALT 2021.
• Mitigating false positives in filters: To adapt or to cache?
  Michael A. Bender, Rathish Das, Martin Farach-Colton, Tianchi Mo, David Tench, Yung Ping Wang.
  APOCS 2021.
• On the robust communication complexity of bipartite matching.
  Sepehr Assadi, Soheil Behnezhad.
  APPROX-RANDOM 2021.
• Improved hitting set for orbit of ROABPs.
  Vishwas Bhargava, Sumanta Ghosh.
  APPROX-RANDOM 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.
• Evaluating fairness of machine learning models under uncertain and incomplete information. [arXiv]
  Pranjal Awasthi, Alex Beutel, Matthäus Kleindessner, Jamie Morgenstern, Xuezhi Wang.
  FAccT 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.
• Parallel sparse LU factorization with machine-learning method on multi-core processors.
  Junsheng Zhou, Wangdong Yang, Minlu Dai, Qinyun Cai, Haotian Wang, Kenli Li.
  ICSAI 2021.
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity.
  Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle.
  ISAAC 2021.
• Towards a theory of confidence in market-based predictions.
  Rupert Freeman, David M. Pennock, Daniel M. Reeves, David M. Rothschild, Bo Waggoner.
  ISIPTA 2021.
• Depth-first search in directed planar graphs, revisited.
  Eric Allender, Archit Chauhan, Samir Datta.
  MFCS 2021.
• RTFE: A recursive temporal fact embedding framework for temporal knowledge graph completion. [arXiv]
  Youri Xu, Haihong E, Meina Song, Wenyu Song, Xiaodong Lv, Haotian Wang, Jinrui Yang.
  NAACL-HLT 2021.
• Dynamic trace estimation. [arXiv]
  Prathamesh Dharangutte, Christopher Musco.
  NeurIPS 2021.
• Vector quotient filters: Overcoming the time/space trade-off in filter design.
  Prashant Pandey, Alex Conway, Joe Durie, Michael A. Bender, Martin Farach-Colton, Rob Johnson.
  SIGMOD Conference 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.
• Approximation algorithms for multi-robot patrol-scheduling with min-max latency. [arXiv]
  Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, Hao-Tsung Yang.
  WAFR 2021.
• On rearrangement of items stored in stacks. [arXiv]
  Mario Szegedy, Jingjin Yu.
  WAFR 2021.

2020

• Preventing arbitrage from collusion when eliciting probabilities.
  Rupert Freeman, David M. Pennock, Dominik Peters, Bo Waggoner.
  AAAI 2020.
• Equalized odds postprocessing under imperfect group information. [arXiv]
  Pranjal Awasthi, Matthäus Kleindessner, Jamie Morgenstern.
  AISTATS 2020.
• A case for data democratization.
  Pranjal Awasthi, Jordana J. George.
  AMCIS 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 Lund, Aditya Potukuchi.
  APPROX-RANDOM 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.
• Ker-I Ko and the study of resource-bounded Kolmogorov complexity.
  Eric Allender.
  Complexity and Approximation 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.
• How to copy files.
  Yang Zhan, Alexander Conway, Yizheng Jiao, Nirjhar Mukherjee, Ian Groombridge, Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Donald E. Porter, Jun Yuan.
  FAST 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.
• Quality-aware and penalty-sensitive opportunistic crowdsensing in mobile relay networks.
  Ailun Song, Jingguang Zhou, Xiaofeng Gao, Haotian Wang, Fan Wu, Guihai Chen.
  GPC 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.
• The impact of data philanthropy on global health when mediated through digital epidemiology.
  Pranjal Awasthi, Jordana J. George.
  ICIS 2020.
• Curvature graph network.
  Ze Ye, Kin Sum Liu, Tengfei Ma, Jie Gao, Chao Chen.
  ICLR 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.
• On the global self-attention mechanism for graph convolutional networks. [arXiv]
  Chen Wang, Chengyuan Deng.
  ICPR 2020.
• Proportionality in approval-based elections with a variable number of winners.
  Rupert Freeman, Anson Kahng, David M. Pennock.
  IJCAI 2020.
• SAG-VAE: End-to-end joint inference of data representations and feature relations.
  Chen Wang, Chengyuan Deng, Vladimir Ivanov.
  IJCNN 2020.
• Differentially private range counting in planar graphs for spatial sensing.
  Abhirup Ghosh, Jiaxin Ding, Rik Sarkar, Jie Gao.
  INFOCOM 2020.
• Distributed human trajectory sensing and partial similarity queries.
  Haotian Wang, Jie Gao.
  IPSN 2020.
• Improved efficiency for covering codes matching the sphere-covering bound. [arXiv]
  Aditya Potukuchi, Yihan Zhang.
  ISIT 2020.
• DEEP-FRI: Sampling outside the box improves soundness. [arXiv]
  Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf.
  ITCS 2020.
• The new complexity landscape around circuit minimization.
  Eric Allender.
  LATA 2020.
• Data inference from encrypted databases: a multi-dimensional order-preserving matching approach. [arXiv]
  Yanjun Pan, Alon Efrat, Ming Li, Boyang Wang, Hanyu Quan, Joseph S. B. Mitchell, Jie Gao, Esther M. Arkin.
  MobiHoc 2020.
• Adversarial robustness via robust low rank representations. [arXiv]
  Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat, Aravindan Vijayaraghavan.
  NeurIPS 2020.
• PAC-Bayes Learning Bounds for Sample-Dependent Priors.
  Pranjal Awasthi, Satyen Kale, Stefani Karp, Mehryar Mohri.
  NeurIPS 2020.
• Efficient active learning of sparse halfspaces with arbitrary bounded noise. [arXiv]
  Chicheng Zhang, Jie Shen, Pranjal Awasthi.
  NeurIPS 2020.
• Lower bounds for distributed sketching of maximal matchings and maximal independent sets.
  Sepehr Assadi, Gillat Kol, Rotem Oshman.
  PODC 2020.
• Timely reporting of heavy hitters using external memory.
  Prashant Pandey, Shikha Singh, Michael A. Bender, Jonathan W. Berry, Martin Farach-Colton, Rob Johnson, Thomas M. Kroeger, Cynthia A. Phillips.
  SIGMOD Conference 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.
• SplinterDB: Closing the bandwidth gap for NVMe key-value stores.
  Alexander Conway, Abhishek Gupta, Vijay Chidambaram, Martin Farach-Colton, Richard P. Spillane, Amy Tai, Rob Johnson.
  USENIX Annual Technical Conference 2020.

2019

• Patrol scheduling against adversaries with varying attack durations.
  Hao-Tsung Yang, Shih-Yu Tsai, Kin Sum Liu, Shan Lin, Jie Gao.
  AAMAS 2019.
• The volatility of weak ties: Co-evolution of selection and influence in social networks.
  Jie Gao, Grant Schoenebeck, Fang-Yi Yu.
  AAMAS 2019.
• Robust matrix completion from quantized observations.
  Jie Shen, Pranjal Awasthi, Ping Li.
  AISTATS 2019.
• Multi-channel assignment and link scheduling for prioritized latency-sensitive applications.
  Shih-Yu Tsai, Hao-Tsung Yang, Kin Sum Liu, Shan Lin, Rezaul Chowdhury, Jie Gao.
  ALGOSENSORS 2019.
• Syntactic separation of subset satisfiability problems. [pdf]
  Eric Allender, Martin Farach-Colton, Meng-Tsung Tsai.
  APPROX-RANDOM 2019.
• On list recovery of high-rate tensor codes. [eccc]
  Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas.
  APPROX-RANDOM 2019.
• Straggling for covert message passing on complete graphs. [arXiv]
  Pei Peng, Nikolas Melissaris, Emina Soljanin, Bill Lee, Anton Maliev, Huafeng Fan.
  Allerton 2019.
• How to accurately and privately identify anomalies.
  Hafiz Salman Asif, Periklis A. Papakonstantinou, Jaideep Vaidya.
  CCS 2019.
• The non-hardness of approximating circuit size.
  Eric Allender, Rahul Ilango, Neekon Vafa.
  CSR 2019.
• Bilu-Linial stability, certified algorithms and the independent set problem. [arXiv]
  Haris Angelidakis, Pranjal Awasthi, Avrim Blum, Vaggos Chatziafratis, Chen Dan.
  ESA 2019.
• Optimizing sensor deployment with line-of-sight constraints: theory and practice.
  Kin Sum Liu, Brent Schiller, Jie Gao, Shan Lin, Joseph S. B. Mitchell.
  EWSN 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.
• Filesystem aging: it's more usage than fullness.
  Alex Conway, Eric Knorr, Yizheng Jiao, Michael A. Bender, William Jannen, Rob Johnson, Donald E. Porter, Martin Farach-Colton.
  HotStorage 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.
• Performing co-membership attacks against deep generative models. [arXiv]
  Kin Sum Liu, Chaowei Xiao, Bo Li, Jie Gao.
  ICDM 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.
• Secretary ranking with minimal inversions. [arXiv]
  Sepehr Assadi, Eric Balkanski, Renato Paes Leme.
  NeurIPS 2019.
• On robustness to adversarial examples and polynomial optimization. [arXiv]
  Pranjal Awasthi, Abhratanu Dutta, Aravindan Vijayaraghavan.
  NeurIPS 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.
• Engineering a high-performance GPU B-tree.
  Muhammad A. Awad, Saman Ashkiani, Rob Johnson, Martin Farach-Colton, John D. Owens.
  PPoPP 2019.
• Efficient beacon placement algorithms for time-of-flight indoor localization.
  Haotian Wang, Niranjini Rajagopal, Anthony Rowe, Bruno Sinopoli, Jie Gao.
  SIGSPATIAL/GIS 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.
• 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

• Robust vertex enumeration for convex hulls in high dimensions. [arXiv]
  Pranjal Awasthi, Bahman Kalantari, Yikai Zhang.
  AISTATS 2018.
• Parameter-hiding order revealing encryption.
  David Cash, Feng-Hao Liu, Adam O'Neill, Mark Zhandry, Cong Zhang.
  ASIACRYPT 2018.
• Worst-case to average case reductions for the distance to a code.
  Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf.
  CCC 2018.
• Star routing: between vehicle routing and vertex cover. [arXiv]
  Diego Delle Donne, Guido Tagliavini.
  COCOA 2018.
• Online labeling: algorithms, lower bounds and open questions.
  Michael E. Saks.
  CSR 2018.
• The full path to full-path indexing.
  Yang Zhan, Alexander Conway, Yizheng Jiao, Eric Knorr, Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Donald E. Porter, Jun Yuan.
  FAST 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.
• Mind the gap (invited paper).
  Martin Farach-Colton.
  FUN 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.
• A dynamic hash table for the GPU. [arXiv]
  Saman Ashkiani, Martin Farach-Colton, John D. Owens.
  IPDPS 2018.
• GPU LSM: a dynamic dictionary data structure for the GPU. [arXiv]
  Saman Ashkiani, Shengren Li, Martin Farach-Colton, Nina Amenta, John D. Owens.
  IPDPS 2018.
• Quotient filters: approximate membership queries on the GPU.
  Afton Geil, Martin Farach-Colton, John D. Owens.
  IPDPS 2018.
• Streaming algorithms for planar convex hulls. [arXiv]
  Martin Farach-Colton, Meng Li, Meng-Tsung Tsai.
  ISAAC 2018.
• A note on the joint entropy of $N/2$-wise independence.
  Amey Bhangale, Aditya Potukuchi.
  ISIT 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.
• Impossibility of order-revealing encryption in idealized models.
  Mark Zhandry, Cong Zhang.
  TCC 2018.
• A ciphertext-size lower bound for order-preserving encryption with limited leakage.
  David Cash, Cong Zhang.
  TCC 2018.

2017

• Consensus on social graphs under increasing peer pressure.
  Justin Semonsen, Christopher Griffin, Anna Cinzia Squicciarini, Sarah Michele Rajtmajer.
  AAMAS 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.
• Dimension spectra of lines. [arXiv]
  Neil Lutz, Donald M. Stull.
  CiE 2017.
• The complexity of complexity.
  Eric Allender.
  Computability and Complexity 2017.
• File systems fated for senescence? Nonsense, says science!
  Alexander Conway, Ainesh Bakshi, Yizheng Jiao, William Jannen, Yang Zhan, Jun Yuan, Michael A. Bender, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Martin Farach-Colton.
  FAST 2017.
• An improved dictatorship test with perfect completeness. [arXiv]
  Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari.
  FSTTCS 2017.
• An ultimatum game model for the evolution of privacy in jointly managed content.
  Sarah Michele Rajtmajer, Anna Cinzia Squicciarini, Jose M. Such, Justin Semonsen, Andrew Belmonte.
  GameSec 2017.
• Irreducibility and deterministic $r$-th root finding over finite fields. [eccc]
  Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena.
  ISSAC 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.
• Dictionaries revisited.
  Martin Farach-Colton.
  SEA 2017.
• A simple yet effective balanced edge partition model for parallel computing.
  Lingda Li, Robel Geda, Ari B. Hayes, Yan-Hao Chen, Pranav Chaudhari, Eddy Z. Zhang, Mario Szegedy.
  SIGMETRICS (Abstracts) 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.
• On the number of ordinary lines determined by sets in complex space. [arXiv]
  Abdul Basit, Zeev Dvir, Shubhangi Saraf, Charles Wolf.
  SoCG 2017.
• Bounding the dimension of points on a line. [arXiv]
  Neil Lutz, Donald M. Stull.
  TAMC 2017.

2016

• Local search for hard SAT formulas: the strength of the polynomial law.
  Sixue Liu, Periklis A. Papakonstantinou.
  AAAI 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.
• What else is revealed by order-revealing encryption?
  F. Betül Durak, Thomas M. DuBuisson, David Cash.
  CCS 2016.
• Combiners for Chosen-Ciphertext Security.
  Cong Zhang, David Cash, Xiuhua Wang, Xiaoqi Yu, Sherman S. M. Chow.
  COCOON 2016.
• Learning and 1-bit compressed sensing under asymmetric noise.
  Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, Hongyang Zhang.
  COLT 2016.
• Optimizing every operation in a write-optimized file system.
  Jun Yuan, Yang Zhan, William Jannen, Prashant Pandey, Amogh Akshintala, Kanchan Chandnani, Pooja Deo, Zardosht Kasheff, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter.
  FAST 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.
• Lazy analytics: let other queries do the work for you.
  William Jannen, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter.
  HotStorage 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.
• Circular Security Reconsidered.
  F. Betül Durak, Serge Vaudenay.
  SECITC 2016.
• Robust positioning patterns.
  Ross Berkowitz, Swastik Kopparty.
  SODA 2016.
• Parallel lookups in string indexes.
  Anders Roy Christiansen, Martin Farach-Colton.
  SPIRE 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.
• Optimizing every operation in a write-optimized file system.
  Jun Yuan, Yang Zhan, William Jannen, Prashant Pandey, Amogh Akshintala, Kanchan Chandnani, Pooja Deo, Zardosht Kasheff, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter.
  USENIX Annual Technical Conference 2016.

2015

• On fortification of projection games. [arXiv]
  Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat.
  APPROX-RANDOM 2015.
• Related randomness attacks for public key cryptosystems.
  Tsz Hon Yuen, Cong Zhang, Sherman S. M. Chow, Siu-Ming Yiu.
  AsiaCCS 2015.
• A characterization of hard-to-cover CSPs. [arXiv]
  Amey Bhangale, Prahladh Harsha, Girish Varma.
  CCC 2015.
• BetrFS: a right-optimized write-optimized file system.
  William Jannen, Jun Yuan, Yang Zhan, Amogh Akshintala, John Esmet, Yizheng Jiao, Ankur Mittal, Prashant Pandey, Phaneendra Reddy, Leif Walsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter.
  FAST 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.
• Complexity of regular functions.
  Eric Allender, Ian Mertz.
  LATA 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.
• Bisector energy and few distinct distances. [arXiv]
  Ben Lund, Adam Sheffer, Frank de Zeeuw.
  SoCG 2015.
• Finding articulation points of large graphs in linear time.
  Martin Farach-Colton, Tsan-sheng Hsu, Meng Li, Meng-Tsung Tsai.
  WADS 2015.

2014

• The garden hose complexity for the equality function. [arXiv]
  Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu.
  AAIM 2014.
• The power of super-logarithmic number of players.
  Arkadev Chattopadhyay, Michael E. Saks.
  APPROX-RANDOM 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.
• Property testing bounds for linear and quadratic functions via parity decision trees.
  Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni.
  CSR 2014.
• Lines missing every random point. [arXiv]
  Jack H. Lutz, Neil Lutz.
  CiE 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.
• Dynamic windows scheduling with reallocation. [arXiv]
  Martin Farach-Colton, Katia Leal, Miguel A. Mosteiro, Christopher Thraves.
  SEA 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.
• Using convex relaxations for efficiently and privately releasing marginals.
  Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar.
  SoCG 2014.