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.
• Accuracy and fairness for web-based content analysis under temporal shifts and delayed labeling.
  Abdulaziz A. Almuzaini, David M. Pennock, Vivek K. Singh.
  WebSci 2024.

2023

• Robust Planning over Restless Groups: Engagement Interventions for a Large-Scale Maternal Telehealth Program.
  Jackson A. Killian, Arpita Biswas, Lily Xu, Shresth Verma, Vineet Nair, Aparna Taneja, Aparna Hegde, Neha Madhiwalla, Paula Rodriguez Diaz, Sonja Johnson-Yu, Milind Tambe.
  AAAI 2023.
• Integer Subspace Differential Privacy. [arXiv]
  Prathamesh Dharangutte, Jie Gao, Ruobin Gong, Fang-Yi Yu.
  AAAI 2023.
• Artificial Prediction Markets Present a Novel Opportunity for Human-AI Collaboration. [arXiv]
  Tatiana Chakravorti, Vaibhav Singh, Sarah Rajtmajer, Michael McLaughlin, Robert Fraleigh, Christopher Griffin, Anthony Kwasnica, David M. Pennock, C. Lee Giles.
  AAMAS 2023.
• Fairness for Workers Who Pull the Arms: An Index Based Policy for Allocation of Restless Bandit Tasks. [arXiv]
  Arpita Biswas, Jackson A. Killian, Paula Rodriguez Diaz, Susobhan Ghosh, Milind Tambe.
  AAMAS 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.
• Mosaic Pages: Big TLB Reach with Small Pages.
  Krishnan Gosakan, Jaehyun Han, William Kuszmaul, Ibrahim N. Mubarek, Nirjhar Mukherjee, Karthik Sriram, Guido Tagliavini, Evan West, Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martin Farach-Colton, Jayneel Gandhi, Rob Johnson, Sudarsun Kannan, Donald E. Porter.
  ASPLOS 2023.
• HeartInsightify: Interpreting Longitudinal Heart Rate Data for Health Insights through Conformal Clustering.
  Prathamesh Dharangutte, Zongxing Xie, Jie Gao, Elinor Schoenfeld, Yindong Hua, Fan Ye.
  BIBM 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.
• Graph peeling semantics.
  James Abello, Haoyang Zhang.
  EDBT/ICDT Workshops 2023.
• Research on dynamic scheduling algorithm for emergency repair of power grid disaster relief based on improved Q-learning.
  Jun Yan, Lei Wang, Weibing Weng, Xiong Fan, Cong Lin, Wanpeng Li.
  EITCE 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.
• An Algorithmic Approach to Address Course Enrollment Challenges. [arXiv]
  Arpita Biswas, Yiduo Ke, Samir Khuller, Quanquan C. Liu.
  FORC 2023.
• A Prototype Hybrid Prediction Market for Estimating Replicability of Published Work. [arXiv]
  Tatiana Chakravorti, Robert Fraleigh, Timothy Fritton, Michael McLaughlin, Vaibhav Singh, Christopher Griffin, Anthony Kwasnica, David M. Pennock, C. Lee Giles, Sarah Rajtmajer.
  HHAI 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.
• Streaming algorithms and lower bounds for estimating correlation clustering cost.
  Sepehr Assadi, Vihan Shah, Chen Wang.
  NeurIPS 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.
• Differentially Private Range Query on Shortest Paths. [arXiv]
  Chengyuan Deng, Jie Gao, Jalaj Upadhyay, Chen Wang.
  WADS 2023.
• DeMEtRIS: Counting (near)-Cliques by Crawling.
  Suman K. Bera, Jayesh Choudhari, Shahrzad Haddadan, Sara Ahmadian.
  WSDM 2023.

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.
• Using Public Data to Predict Demand for Mobile Health Clinics.
  Haipeng Chen, Susobhan Ghosh, Gregory Fan, Nikhil Behari, Arpita Biswas, Mollie Williams, Nancy E. Oriol, Milind Tambe.
  AAAI 2022.
• Optimal local bayesian differential privacy over Markov chains. [arXiv]
  Darshan Chakrabarti, Jie Gao, Aditya Saraf, Grant Schoenebeck, Fang-Yi Yu.
  AAMAS 2022.
• Efficient Algorithms for Finite Horizon and Streaming Restless Multi-Armed Bandit Problems. [arXiv]
  Aditya S. Mate, Arpita Biswas, Christoph Siebenbrunner, Susobhan Ghosh, Milind Tambe.
  AAMAS 2022.
• On Achieving Leximin Fairness and Stability in Many-to-One Matchings. [arXiv]
  Shivika Narang, Arpita Biswas, Yadati Narahari.
  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.
• Collusion-Resistant Functional Encryption for RAMs.
  Prabhanjan Ananth, Kai-Min Chung, Xiong Fan, Luowen Qian.
  ASIACRYPT 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.
• 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.
• Ranked Prioritization of Groups in Combinatorial Bandit Allocation. [arXiv]
  Lily Xu, Arpita Biswas, Fei Fang, Milind Tambe.
  IJCAI 2022.
• Clustering of Trajectories using Non-Parametric Conformal DBSCAN Algorithm.
  Haotian Wang, Jie Gao, Min-ge Xie.
  IPSN 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.
• Single-pass streaming lower bounds for multi-armed bandits exploration with instance-sensitive sample complexity.
  Sepehr Assadi, Chen Wang.
  NeurIPS 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 ℓ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.
• 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.
• Restless and uncertain: Robust policies for restless bandits via deep multi-agent reinforcement learning. [arXiv]
  Jackson A. Killian, Lily Xu, Arpita Biswas, Milind Tambe.
  UAI 2022.
• The Drift of #MyBodyMyChoice Discourse on Twitter. [arXiv]
  Cristina Menghini, Justin Uhr, Shahrzad Haddadan, Ashley Champagne, Björn Sandstede, Sohini Ramachandran.
  WebSci 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.
• Learning Index Policies for Restless Bandits with Application to Maternal Healthcare.
  Arpita Biswas, Gaurav Aggarwal, Pradeep Varakantham, Milind Tambe.
  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.
• Ensuring Fairness under Prior Probability Shifts. [arXiv]
  Arpita Biswas, Suvam Mukherjee.
  AIES 2021.
• Differentially Private Analysis on Graph Streams.
  Jalaj Upadhyay, Sarvagya Upadhyay, Raman Arora.
  AISTATS 2021.
• A deep conditioning treatment of neural networks. [arXiv]
  Naman Agarwal, Pranjal Awasthi, Satyen Kale.
  ALT 2021.
• Accurately and Privately Reporting Crowdsensed COVID-19 Data.
  Hafiz Salman Asif, Periklis A. Papakonstantinou, Stephanie Shiau, Vivek K. Singh, Jaideep Vaidya.
  AMIA 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 Cities: Their Buildings, Waves, and Fragments.
  James Abello, Daniel Nakhimovich, Chengguizi Han, Mridul Aanjaneya.
  EDBT/ICDT Workshops 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.
• Application-driven Privacy-preserving Data Publishing with Correlated Attributes. [arXiv]
  Aria Rezaei, Chaowei Xiao, Jie Gao, Bo Li, Sirajum Munir.
  EWSN 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.
• A Framework for Private Matrix Analysis in Sliding Window Model.
  Jalaj Upadhyay, Sarvagya Upadhyay.
  ICML 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.
• Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcare. [arXiv]
  Arpita Biswas, Gaurav Aggarwal, Pradeep Varakantham, Milind Tambe.
  IJCAI 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.
• Q-Learning Lagrange Policies for Multi-Action Restless Bandits.
  Jackson A. Killian, Arpita Biswas, Sanket Shah, Milind Tambe.
  KDD 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.
• Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds. [arXiv]
  Shahrzad Haddadan, Yue Zhuang, Cyrus Cousins, Eli Upfal.
  NeurIPS 2021.
• Influencers and the Giant Component: The Fundamental Hardness in Privacy Protection for Socially Contagious Attributes. [arXiv]
  Aria Rezaei, Jie Gao, Anand D. Sarwate.
  SDM 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.
• RePBubLik: Reducing Polarized Bubble Radius with Link Insertions.
  Shahrzad Haddadan, Cristina Menghini, Matteo Riondato, Eli Upfal.
  WSDM 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 (Δ+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.
• The Role of In-Group Bias and Balanced Data: A Comparison of Human and Machine Recidivism Risk Predictions.
  Arpita Biswas, Marta Kolczynska, Saana Rantanen, Polina Rozenshtein.
  COMPASS 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.
• Graph Waves. [arXiv]
  James Abello, Daniel Nakhimovich.
  EDBT/ICDT Workshops 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.
• A theoretical analysis of graph evolution caused by triadic closure and algorithmic implications.
  Sara Ahmadian, Shahrzad Haddadan.
  IEEE BigData 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.
• FairRec: Two-Sided Fairness for Personalized Recommendations in Two-Sided Platforms. [arXiv]
  Gourab K. Patro, Arpita Biswas, Niloy Ganguly, Krishna P. Gummadi, Abhijnan Chakraborty.
  WWW 2020.

2019

• Matroid Constrained Fair Allocation Problem.
  Arpita Biswas, Siddharth Barman.
  AAAI 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.
• Fairness Through the Lens of Proportional Equality.
  Arpita Biswas, Suvam Mukherjee.
  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 AC0[⊕] 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.
• On Privacy of Socially Contagious Attributes. [arXiv]
  Aria Rezaei, 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.
• Atlas: local graph exploration in a global context.
  James Abello, Fred Hohman, Varun Bezzam, Duen Horng Chau.
  IUI 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 (Δ+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

• Groupwise Maximin Fair Allocation of Indivisible Goods. [arXiv]
  Siddharth Barman, Arpita Biswas, Sanath Kumar Krishna Murthy, Yadati Narahari.
  AAAI 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.
• Impact of Detour-Aware Policies on Maximizing Profit in Ridesharing. [arXiv]
  Arpita Biswas, Ragavendran Gopalakrishnan, Theja Tulabandhula, Asmita Metrewar, Koyel Mukherjee, Raja Subramaniam Thangaraj.
  ATT@IJCAI 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.
• 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.
• Fair Division Under Cardinality Constraints. [arXiv]
  Arpita Biswas, Siddharth Barman.
  IJCAI 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.
• Mallows Models for Top-k Lists.
  Flavio Chierichetti, Anirban Dasgupta, Shahrzad Haddadan, Ravi Kumar, Silvio Lattanzi.
  NeurIPS 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.
• 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.
• Profit Optimization in Commercial Ridesharing.
  Arpita Biswas, Ragavendran Gopalakrishnan, Theja Tulabandhula, Koyel Mukherjee, Asmita Metrewar, Thangaraj Rajasubramaniam.
  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.
• Trajectory-Based Multi-hop Relay Deployment in Wireless Networks.
  Shilei Tian, Haotian Wang, Sha Li, Fan Wu, Guihai Chen.
  COCOA 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.
• Approximation Designs for Cooperative Relay Deployment in Wireless Networks.
  Haotian Wang, Shilei Tian, Xiaofeng Gao, Lidong Wu, Guihai Chen.
  ICDCS 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.
• FACETS: Adaptive Local Exploration of Large Graphs.
  Robert S. Pienta, Minsuk Kahng, Zhiyuan Lin, Jilles Vreeken, Partha P. Talukdar, James Abello, Ganesh Parameswaran, Duen Horng Chau.
  SDM 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 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.
• 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.
• Managing Overstaying Electric Vehicles in Park-and-Charge Facilities. [arXiv]
  Arpita Biswas, Ragavendran Gopalakrishnan, Partha Dutta.
  IJCAI 2016.
• Demand Prediction and Placement Optimization for Electric Vehicle Charging Stations. [arXiv]
  Ragavendran Gopalakrishnan, Arpita Biswas, Alefiya Lightwala, Skanda Vasudevan, Partha Dutta, Abhishek Tripathi.
  IJCAI 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

• A Truthful Budget Feasible Multi-Armed Bandit Mechanism for Crowdsourcing Time Critical Tasks.
  Arpita Biswas, Shweta Jain, Debmalya Mandal, Y. Narahari.
  AAMAS 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.
• Scalable graph exploration and visualization: Sensemaking challenges and opportunities.
  Robert S. Pienta, James Abello, Minsuk Kahng, Duen Horng Chau.
  BigComp 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.
• PISCES: Participatory Incentive Strategies for Effective Community Engagement in Smart Cities.
  Arpita Biswas, Deepthi Chander, Koustuv Dasgupta, Koyel Mukherjee, Mridula Singh, Tridib Mukherjee.
  HCOMP 2015.
• Simultaneous approximation of constraint satisfaction problems. [arXiv]
  Amey Bhangale, Swastik Kopparty, Sushant Sachdeva.
  ICALP 2015.
• Efficient and Time Scale-Invariant Detection of Correlated Activity in Communication Networks.
  Brian Thompson, James Abello.
  ICDM Workshops 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.