Publications of the Stanford Theory Group

2023

BiB
TeX
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs.
AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, Salil P. Vadhan.
In proc. FOCS, pp. 846-854, 2023.

BiB
TeX
Distortion in metric matching with ordinal preferences.
Nima Anari, Moses Charikar, Prasanna Ramakrishnan.
In proc. EC, pp. 90-110, 2023.

BiB
TeX
Quadratic Speedups in Parallel Sampling from Determinantal Distributions.
Nima Anari, Callum Burgess, Kevin Tian, Thuy-Duong Vuong.
In proc. SPAA, pp. 367-377, 2023.

BiB
TeX
Parallel Discrete Sampling via Continuous Walks.
Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, Katherine Yu.
In proc. STOC, pp. 103-116, 2023.

BiB
TeX
Sequential Submodular Maximization and Applications to Ranking an Assortment of Products.
Arash Asadpour, Rad Niazadeh, Amin Saberi, Ali Shameli.
In Oper. Res., vol. 71, no. 4, pp. 1154-1170, 2023.

BiB
TeX
Edge-Weighted Online Windowed Matching.
Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, Chris Sholley.
In Math. Oper. Res., vol. 48, no. 2, pp. 999-1016, 2023.

BiB
TeX
Multitask Learning via Shared Features: Algorithms and Hardness.
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan R. Ullman, Lydia Zakynthinou.
In proc. COLT, pp. 747-772, 2023.

BiB
TeX
Local Computation Algorithms for Maximum Matching: New Lower Bounds.
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein.
In proc. FOCS, pp. 2322-2335, 2023.

BiB
TeX
Single-Pass Streaming Algorithms for Correlation Clustering.
Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan.
In proc. SODA, pp. 819-849, 2023.

BiB
TeX
Beating Greedy Matching in Sublinear Time.
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi.
In proc. SODA, pp. 3900-3945, 2023.

BiB
TeX
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching.
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein.
In proc. STOC, pp. 267-280, 2023.

BiB
TeX
On complex roots of the independence polynomial.
Ferenc Bencs, Péter Csikvári, Piyush Srivastava, Jan Vondrák.
In proc. SODA, pp. 675-699, 2023.

BiB
TeX
A strong composition theorem for junta complexity and the boosting of property testers.
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan.
In proc. FOCS, pp. 1757-1777, 2023.

BiB
TeX
Certification with an NP Oracle.
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan.
In proc. ITCS, pp. 18:1-18:22, 2023.

BiB
TeX
Lifting Uniform Learners via Distributional Decomposition.
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan.
In proc. STOC, pp. 1755-1767, 2023.

BiB
TeX
Post-Quantum Single Secret Leader Election (SSLE) from Publicly Re-Randomizable Commitments.
Dan Boneh, Aditi Partap, Lior Rotem.
In proc. AFT, pp. 26:1-26:23, 2023.

BiB
TeX
Arithmetic Sketching.
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai.
In proc. CRYPTO (1), pp. 171-202, 2023.

BiB
TeX
A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies.
Dan Boneh, Jiaxin Guan, Mark Zhandry.
In proc. EUROCRYPT (5), pp. 507-531, 2023.

BiB
TeX
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling.
Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, Kevin Tian.
In proc. ICML, pp. 2932-2952, 2023.

BiB
TeX
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.
Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford.
In proc. FOCS, pp. 503-514, 2023.

BiB
TeX
Dynamic Maxflow via Dynamic Interior Point Methods.
Jan van den Brand, Yang P. Liu, Aaron Sidford.
In proc. STOC, pp. 1215-1228, 2023.

BiB
TeX
Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI).
Eric Budish, Ruiquan Gao, Abraham Othman, Aviad Rubinstein, Qianfan Zhang.
In proc. EC, pp. 337-368, 2023.

BiB
TeX
One-sided Matrix Completion from Two Observations Per Row.
Steven Cao, Percy Liang, Gregory Valiant.
In proc. ICML, pp. 3599-3624, 2023.

BiB
TeX
ReSQueing Parallel and Private Stochastic Convex Optimization.
Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian.
In proc. FOCS, pp. 2031-2058, 2023.

BiB
TeX
Fast Algorithms for a New Relaxation of Optimal Transport.
Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten.
In proc. COLT, pp. 4831-4862, 2023.

BiB
TeX
A Characterization of List Learnability.
Moses Charikar, Chirag Pabbaraju.
In proc. STOC, pp. 1713-1726, 2023.

BiB
TeX
HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates.
Binyi Chen, Benedikt Bünz, Dan Boneh, Zhenfei Zhang.
In proc. EUROCRYPT (2), pp. 499-530, 2023.

BiB
TeX
Repairing Reed-Solomon Codes over Prime Fields via Exponential Sums.
Roni Con, Noah Shutty, Itzhak Tamo, Mary Wootters.
In proc. ISIT, pp. 1330-1335, 2023.

BiB
TeX
Fairness and Incentive Compatibility via Percentage Fees.
Shahar Dobzinski, Sigal Oren, Jan Vondrák.
In proc. EC, pp. 517-535, 2023.

BiB
TeX
From the Real Towards the Ideal: Risk Prediction in a Better World.
Cynthia Dwork, Omer Reingold, Guy N. Rothblum.
In proc. FORC, pp. 1:1-1:17, 2023.

BiB
TeX
Approximating Nash Social Welfare by Matching and Local Search.
Jugal Garg, Edin Husic, Wenzheng Li, László A. Végh, Jan Vondrák.
In proc. STOC, pp. 1298-1310, 2023.

BiB
TeX
Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence.
Margalit Glasgow, Colin Wei, Mary Wootters, Tengyu Ma.
In proc. ICLR, 2023.

BiB
TeX
Loss Minimization Through the Lens Of Outcome Indistinguishability.
Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, Udi Wieder.
In proc. ITCS, pp. 60:1-60:20, 2023.

BiB
TeX
Low Sample Complexity Participatory Budgeting.
Mohak Goyal, Sukolsak Sakshuwong, Sahasrajit Sarmasarkar, Ashish Goel.
In proc. ICALP, pp. 70:1-70:20, 2023.

BiB
TeX
Finding the Right Curve: Optimal Design of Constant Function Market Makers.
Mohak Goyal, Geoffrey Ramseyer, Ashish Goel, David Mazières.
In proc. EC, pp. 783-812, 2023.

BiB
TeX
A Mechanism for Participatory Budgeting with Funding Constraints and Project Interactions.
Mohak Goyal, Sahasrajit Sarmasarkar, Ashish Goel.
In proc. WINE, pp. 329-347, 2023.

BiB
TeX
Sparse Submodular Function Minimization.
Andrei Graur, Haotian Jiang, Aaron Sidford.
In proc. FOCS, pp. 2071-2080, 2023.

BiB
TeX
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria.
Mika Göös, Aviad Rubinstein.
In SIAM J. Comput., vol. 52, no. 6, pp. S18-316, 2023.

BiB
TeX
Faster Submodular Maximization for Several Classes of Matroids.
Monika Henzinger, Paul Liu, Jan Vondrák, Da Wei Zheng.
In proc. ICALP, pp. 74:1-74:18, 2023.

BiB
TeX
Envy-Free Cake-Cutting for Four Agents.
Alexandros Hollender, Aviad Rubinstein.
In proc. FOCS, pp. 113-122, 2023.

BiB
TeX
Generative Models of Huge Objects.
Lunjia Hu, Inbal Livni Navon, Omer Reingold.
In proc. CCC, pp. 5:1-5:20, 2023.

BiB
TeX
Omnipredictors for Constrained Optimization.
Lunjia Hu, Inbal Rachel Livni Navon, Omer Reingold, Chutong Yang.
In proc. ICML, pp. 13497-13527, 2023.

BiB
TeX
Sparsifying Sums of Norms.
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford.
In proc. FOCS, pp. 1953-1962, 2023.

BiB
TeX
Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification.
Arun Jambulapati, Yang P. Liu, Aaron Sidford.
In proc. STOC, pp. 196-206, 2023.

BiB
TeX
Moments, Random Walks, and Limits for Spectrum Approximation.
Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh.
In proc. COLT, pp. 5373-5394, 2023.

BiB
TeX
The Complexity of Infinite-Horizon General-Sum Stochastic Games.
Yujia Jin, Vidya Muthukumar, Aaron Sidford.
In proc. ITCS, pp. 76:1-76:20, 2023.

BiB
TeX
Improved girth approximation in weighted undirected graphs.
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick.
In proc. SODA, pp. 2242-2255, 2023.

BiB
TeX
Semi-Random Sparse Recovery in Nearly-Linear Time.
Jonathan A. Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, Kevin Tian.
In proc. COLT, pp. 2352-2398, 2023.

BiB
TeX
Matrix Completion in Almost-Verification Time.
Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian.
In proc. FOCS, pp. 2102-2128, 2023.

BiB
TeX
Properly learning decision trees with queries is NP-hard.
Caleb Koch, Carmen Strassle, Li-Yang Tan.
In proc. FOCS, pp. 2383-2407, 2023.

BiB
TeX
Superpolynomial lower bounds for decision tree learning and testing.
Caleb Koch, Carmen Strassle, Li-Yang Tan.
In proc. SODA, pp. 1962-1994, 2023.

BiB
TeX
Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes.
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters.
In SIAM J. Comput., vol. 52, no. 3, pp. 794-840, 2023.

BiB
TeX
Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract).
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant.
In proc. IJCAI, pp. 6468-6473, 2023.

BiB
TeX
Bidding Strategies for Proportional Representation in Advertisement Campaigns.
Inbal Livni Navon, Charlotte Peale, Omer Reingold, Judy Hanwen Shen.
In proc. FORC, pp. 3:1-3:22, 2023.

BiB
TeX
Revisiting the Nova Proof System on a Cycle of Curves.
Wilson D. Nguyen, Dan Boneh, Srinath T. V. Setty.
In proc. AFT, pp. 18:1-18:22, 2023.

BiB
TeX
Towards an Optimal Contention Resolution Scheme for Matchings.
Pranav Nuti, Jan Vondrák.
In proc. IPCO, pp. 378-392, 2023.

BiB
TeX
Secretary Problems: The Power of a Single Sample.
Pranav Nuti, Jan Vondrák.
In proc. SODA, pp. 2015-2029, 2023.

BiB
TeX
Near Optimal Memory-Regret Tradeoff for Online Learning.
Binghui Peng, Aviad Rubinstein.
In proc. FOCS, pp. 1171-1194, 2023.

BiB
TeX
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window).
Binghui Peng, Aviad Rubinstein.
In proc. SOSA, pp. 261-271, 2023.

BiB
TeX
Do Users Write More Insecure Code with AI Assistants?
Neil Perry, Megha Srivastava, Deepak Kumar, Dan Boneh.
In proc. CCS, pp. 2785-2799, 2023.

BiB
TeX
Online Pen Testing.
Mingda Qiao, Gregory Valiant.
In proc. ITCS, pp. 91:1-91:26, 2023.

BiB
TeX
SPEEDEX: A Scalable, Parallelizable, and Economically Efficient Decentralized EXchange.
Geoffrey Ramseyer, Ashish Goel, David Mazières.
In proc. NSDI, pp. 849-875, 2023.

BiB
TeX
Beyond Worst-Case Budget-Feasible Mechanism Design.
Aviad Rubinstein, Junyao Zhao.
In proc. ITCS, pp. 93:1-93:22, 2023.

BiB
TeX
Vector Commitments with Efficient Updates.
Ertem Nusret Tas, Dan Boneh.
In proc. AFT, pp. 29:1-29:23, 2023.

BiB
TeX
Cryptoeconomic Security for Data Availability Committees.
Ertem Nusret Tas, Dan Boneh.
In proc. FC, pp. 310-326, 2023.

BiB
TeX
R-Pool and Settlement Markets for Recoverable ERC-20R Tokens.
Kaili Wang, Qinchen Wang, Calvin Cai, Dan Boneh.
In proc. DeFi@CCS, pp. 49-54, 2023.
2022

BiB
TeX
The Value of Excess Supply in Spatial Matching Markets.
Mohammad Akbarpour, Yeganeh Alimohammadi, Shengwu Li, Amin Saberi.
In proc. EC, pp. 62, 2022.

BiB
TeX
Algorithms Using Local Graph Features to Predict Epidemics.
Yeganeh Alimohammadi, Christian Borgs, Amin Saberi.
In proc. SODA, pp. 3430-3451, 2022.

BiB
TeX
From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization.
Nima Anari, Thuy-Duong Vuong.
In proc. COLT, pp. 5596-5618, 2022.

BiB
TeX
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence.
Nima Anari, Yang P. Liu, Thuy-Duong Vuong.
In proc. FOCS, pp. 123-134, 2022.

BiB
TeX
Domain Sparsification of Discrete Distributions Using Entropic Independence.
Nima Anari, Michal Derezinski, Thuy-Duong Vuong, Elizabeth Yang.
In proc. ITCS, pp. 5:1-5:23, 2022.

BiB
TeX
Entropic independence: optimal mixing of down-up random walks.
Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Thuy-Duong Vuong.
In proc. STOC, pp. 1418-1430, 2022.

BiB
TeX
Sequential Submodular Maximization and Applications to Ranking an Assortment of Products.
Arash Asadpour, Rad Niazadeh, Amin Saberi, Ali Shameli.
In proc. EC, pp. 817, 2022.

BiB
TeX
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space.
Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian.
In proc. SODA, pp. 627-669, 2022.

BiB
TeX
Communication complexity of approximate Nash equilibria.
Yakov Babichenko, Aviad Rubinstein.
In Games Econ. Behav., vol. 134, pp. 376-398, 2022.

BiB
TeX
An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model.
Eric Balkanski, Aviad Rubinstein, Yaron Singer.
In Oper. Res., vol. 70, no. 5, pp. 2967-2981, 2022.

BiB
TeX
The Limitations of Optimization from Samples.
Eric Balkanski, Aviad Rubinstein, Yaron Singer.
In J. ACM, vol. 69, no. 3, pp. 21:1-21:33, 2022.

BiB
TeX
Almost 3-Approximate Correlation Clustering in Constant Rounds.
Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan.
In proc. FOCS, pp. 720-731, 2022.

BiB
TeX
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun.
In proc. ICALP, pp. 20:1-20:20, 2022.

BiB
TeX
On the power of adaptivity in statistical adversaries.
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan.
In proc. COLT, pp. 5030-5061, 2022.

BiB
TeX
Reconstructing Decision Trees.
Guy Blanc, Jane Lange, Li-Yang Tan.
In proc. ICALP, pp. 24:1-24:17, 2022.

BiB
TeX
A query-optimal algorithm for finding counterfactuals.
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan.
In proc. ICML, pp. 2075-2090, 2022.

BiB
TeX
Popular decision tree algorithms are provably noise tolerant.
Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan.
In proc. ICML, pp. 2091-2106, 2022.

BiB
TeX
The query complexity of certification.
Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan.
In proc. STOC, pp. 623-636, 2022.

BiB
TeX
Properly Learning Decision Trees in almost Polynomial Time.
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan.
In J. ACM, vol. 69, no. 6, pp. 39:1-39:19, 2022.

BiB
TeX
Threshold Signatures with Private Accountability.
Dan Boneh, Chelsea Komlo.
In proc. CRYPTO (4), pp. 551-581, 2022.

BiB
TeX
Faster maxflow via improved dynamic spectral vertex sparsifiers.
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford.
In proc. STOC, pp. 543-556, 2022.

BiB
TeX
RECAPP: Crafting a More Efficient Catalyst for Convex Optimization.
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford.
In proc. ICML, pp. 2658-2685, 2022.

BiB
TeX
Optimal and Adaptive Monteiro-Svaiter Acceleration.
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, Aaron Sidford.
In proc. NeurIPS, 2022.

BiB
TeX
Improved Lower Bounds for Submodular Function Minimization.
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford.
In proc. FOCS, pp. 245-254, 2022.

BiB
TeX
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood.
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford.
In proc. NeurIPS, 2022.

BiB
TeX
Polylogarithmic Sketches for Clustering.
Moses Charikar, Erik Waingarten.
In proc. ICALP, pp. 38:1-38:20, 2022.

BiB
TeX
On the Efficient Implementation of High Accuracy Optimality of Profile Maximum Likelihood.
Moses Charikar, Zhihao Jiang, Kirankumar Shiragur, Aaron Sidford.
In proc. NeurIPS, 2022.

BiB
TeX
Near-Optimal Explainable k-Means for All Dimensions.
Moses Charikar, Lunjia Hu.
In proc. SODA, pp. 2580-2606, 2022.

BiB
TeX
Metric Distortion Bounds for Randomized Social Choice.
Moses Charikar, Prasanna Ramakrishnan.
In proc. SODA, pp. 2986-3004, 2022.

BiB
TeX
On the hardness of dominant strategy mechanism design.
Shahar Dobzinski, Shiri Ron, Jan Vondrák.
In proc. STOC, pp. 690-703, 2022.

BiB
TeX
High-Probability List-Recovery, and Applications to Heavy Hitters.
Dean Doron, Mary Wootters.
In proc. ICALP, pp. 55:1-55:17, 2022.

BiB
TeX
Beyond Bernoulli: Generating Random Outcomes that cannot be Distinguished from Nature.
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona.
In proc. ALT, pp. 342-380, 2022.

BiB
TeX
Clarion: Anonymous Communication from Multiparty Shuffling Protocols.
Saba Eskandarian, Dan Boneh.
In proc. NDSS, 2022.

BiB
TeX
Computing Lewis Weights to High Precision.
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, Aaron Sidford.
In proc. SODA, pp. 2723-2742, 2022.

BiB
TeX
Near-Optimal Bayesian Online Assortment of Reusable Resources.
Yiding Feng, Rad Niazadeh, Amin Saberi.
In proc. EC, pp. 964-965, 2022.

BiB
TeX
On the Download Rate of Homomorphic Secret Sharing.
Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, Mary Wootters.
In proc. ITCS, pp. 71:1-71:22, 2022.

BiB
TeX
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes.
Shivam Garg, Dimitris Tsipras, Percy Liang, Gregory Valiant.
In proc. NeurIPS, 2022.

BiB
TeX
Opinion Change or Differential Turnout: Austin's Budget Feedback Exercise and the Police Department.
Lodewijk L. Gelauff, Ashish Goel.
In proc. EAAMO, pp. 10:1-10:19, 2022.

BiB
TeX
Asynchronous Distributed Optimization with Stochastic Delays.
Margalit R. Glasgow, Mary Wootters.
In proc. AISTATS, pp. 9247-9279, 2022.

BiB
TeX
Multicalibrated Partitions for Importance Weights.
Parikshit Gopalan, Omer Reingold, Vatsal Sharan, Udi Wieder.
In proc. ALT, pp. 408-435, 2022.

BiB
TeX
Omnipredictors.
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, Udi Wieder.
In proc. ITCS, pp. 79:1-79:21, 2022.

BiB
TeX
Bounds for List-Decoding and List-Recovery of Random Linear Codes.
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 68, no. 2, pp. 923-939, 2022.

BiB
TeX
Threshold Rates for Properties of Random Codes.
Venkatesan Guruswami, Jonathan Moshieff, Nicolas Resch, Shashwat Silas, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 68, no. 2, pp. 905-922, 2022.

BiB
TeX
Leximax Approximations and Representative Cohort Selection.
Monika Henzinger, Charlotte Peale, Omer Reingold, Judy Hanwen Shen.
In proc. FORC, pp. 2:1-2:22, 2022.

BiB
TeX
Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability.
Lunjia Hu, Charlotte Peale, Omer Reingold.
In proc. ALT, pp. 515-552, 2022.

BiB
TeX
Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching.
Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian.
In proc. ICALP, pp. 77:1-77:20, 2022.

BiB
TeX
Improved iteration complexities for overconstrained p-norm regression.
Arun Jambulapati, Yang P. Liu, Aaron Sidford.
In proc. STOC, pp. 529-542, 2022.

BiB
TeX
Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods.
Yujia Jin, Aaron Sidford, Kevin Tian.
In proc. COLT, pp. 4362-4415, 2022.

BiB
TeX
Algorithmic trade-offs for girth approximation in undirected graphs.
Avi Kadria, Liam Roditty, Aaron Sidford, Virginia Vassilevska Williams, Uri Zwick.
In proc. SODA, pp. 1471-1492, 2022.

BiB
TeX
Fixed-Price Approximations in Bilateral Trade.
Zi Yang Kang, Francisco Pernice, Jan Vondrák.
In proc. SODA, pp. 2964-2985, 2022.

BiB
TeX
Lower bounds on the redundancy of linear codes with disjoint repair groups.
Sankeerth Rao Karingula, Alexander Vardy, Mary Wootters.
In proc. ISIT, pp. 975-979, 2022.

BiB
TeX
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales.
Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan.
In proc. COLT, pp. 2431-2540, 2022.

BiB
TeX
The Stationary Prophet Inequality Problem.
Kristen Kessel, Ali Shameli, Amin Saberi, David Wajc.
In proc. EC, pp. 243-244, 2022.

BiB
TeX
The Composition Complexity of Majority.
Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan.
In proc. CCC, pp. 19:1-19:26, 2022.

BiB
TeX
Improved batch code lower bounds.
Ray Li, Mary Wootters.
In proc. ISIT, pp. 1596-1599, 2022.

BiB
TeX
Efficient Convex Optimization Requires Superlinear Memory.
Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant.
In proc. COLT, pp. 2390-2430, 2022.

BiB
TeX
A Generalization of the Satisfiability Coding Lemma and Its Applications.
Milan Mossé, Harry Sha, Li-Yang Tan.
In proc. SAT, pp. 9:1-9:18, 2022.

BiB
TeX
Fooling Polytopes.
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan.
In J. ACM, vol. 69, no. 2, pp. 9:1-9:37, 2022.

BiB
TeX
Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets.
Alex Ozdemir, Dan Boneh.
In proc. USENIX Security Symposium, pp. 4291-4308, 2022.

BiB
TeX
On the complexity of dynamic mechanism design.
Christos H. Papadimitriou, George Pierrakos, Alexandros Psomas, Aviad Rubinstein.
In Games Econ. Behav., vol. 134, pp. 399-427, 2022.

BiB
TeX
Technical Note - Online Hypergraph Matching with Delays.
Marco Pavone, Amin Saberi, Maximilian Schiffer, Matt Wu Tsao.
In Oper. Res., vol. 70, no. 4, pp. 2194-2212, 2022.

BiB
TeX
Efficient Capacity-Achieving Codes for General Repeat Channels.
Francisco Pernice, Ray Li, Mary Wootters.
In proc. ISIT, pp. 3097-3102, 2022.

BiB
TeX
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy.
Tristan Pollner, Mohammad Roghani, Amin Saberi, David Wajc.
In proc. EC, pp. 321-322, 2022.

BiB
TeX
Beating the Folklore Algorithm for Dynamic Matching.
Mohammad Roghani, Amin Saberi, David Wajc.
In proc. ITCS, pp. 111:1-111:23, 2022.

BiB
TeX
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation.
Aviad Rubinstein, Junyao Zhao.
In proc. ICALP, pp. 106:1-106:17, 2022.

BiB
TeX
Budget-Smoothed Analysis for Submodular Maximization.
Aviad Rubinstein, Junyao Zhao.
In proc. ITCS, pp. 113:1-113:23, 2022.

BiB
TeX
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas.
Rocco A. Servedio, Li-Yang Tan.
In Theory Comput., vol. 18, pp. 1-46, 2022.

BiB
TeX
Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data.
Noah Shutty, Mary Wootters.
In proc. ITCS, pp. 117:1-117:19, 2022.

BiB
TeX
Local Density Estimation in High Dimensions.
Xian Wu, Moses Charikar, Vishnu Natchu.
In Math. Oper. Res., vol. 47, no. 4, pp. 2614-2640, 2022.

BiB
TeX
zkBridge: Trustless Cross-chain Bridges Made Practical.
Tiancheng Xie, Jiaheng Zhang, Zerui Cheng, Fan Zhang, Yupeng Zhang, Yongzheng Jia, Dan Boneh, Dawn Song.
In proc. CCS, pp. 3003-3017, 2022.
2021

BiB
TeX
Fractionally log-concave and sector-stable polynomials: counting planar matchings and more.
Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, Thuy-Duong Vuong.
In proc. STOC, pp. 433-446, 2021.

BiB
TeX
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood.
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. COLT, pp. 93-158, 2021.

BiB
TeX
Sampling Arborescences in Parallel.
Nima Anari, Nathan Hu, Amin Saberi, Aaron Schild.
In proc. ITCS, pp. 83:1-83:18, 2021.

BiB
TeX
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood.
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. COLT, pp. 93-158, 2021.

BiB
TeX
Sampling Arborescences in Parallel.
Nima Anari, Nathan Hu, Amin Saberi, Aaron Schild.
In proc. ITCS, pp. 83:1-83:18, 2021.

BiB
TeX
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests.
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, Thuy-Duong Vuong.
In proc. STOC, pp. 408-420, 2021.

BiB
TeX
Log-concave polynomials in theory and applications (tutorial).
Nima Anari, Cynthia Vinzant.
In proc. STOC, pp. 12, 2021.

BiB
TeX
Tiered Random Matching Markets: Rank Is Proportional to Popularity.
Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao.
In proc. ITCS, pp. 46:1-46:16, 2021.

BiB
TeX
Stochastic Bias-Reduced Gradient Methods.
Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford.
In proc. NeurIPS, pp. 10810-10822, 2021.

BiB
TeX
Settling the complexity of Nash equilibrium in congestion games.
Yakov Babichenko, Aviad Rubinstein.
In proc. STOC, pp. 1426-1437, 2021.

BiB
TeX
Decision Tree Heuristics Can Fail, Even in the Smoothed Setting.
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 45:1-45:16, 2021.

BiB
TeX
Multiway Online Correlated Selection.
Guy Blanc, Moses Charikar.
In proc. FOCS, pp. 1277-1284, 2021.

BiB
TeX
Properly learning decision trees in almost polynomial time.
Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan.
In proc. FOCS, pp. 920-929, 2021.

BiB
TeX
Learning Stochastic Decision Trees.
Guy Blanc, Jane Lange, Li-Yang Tan.
In proc. ICALP, pp. 30:1-30:16, 2021.

BiB
TeX
Provably efficient, succinct, and precise explanations.
Guy Blanc, Jane Lange, Li-Yang Tan.
In proc. NeurIPS, pp. 6129-6141, 2021.

BiB
TeX
Query strategies for priced information, revisited.
Guy Blanc, Jane Lange, Li-Yang Tan.
In proc. SODA, pp. 1638-1650, 2021.

BiB
TeX
Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments.
Dan Boneh, Justin Drake, Ben Fisch, Ariel Gabizon.
In proc. CRYPTO (1), pp. 649-680, 2021.

BiB
TeX
Lightweight Techniques for Private Heavy Hitters.
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai.
In proc. SP, pp. 762-776, 2021.

BiB
TeX
Noise and the Frontier of Quantum Supremacy.
Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu.
In proc. FOCS, pp. 1308-1317, 2021.

BiB
TeX
Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances.
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang.
In proc. STOC, pp. 859-869, 2021.

BiB
TeX
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss.
Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford.
In proc. COLT, pp. 866-882, 2021.

BiB
TeX
Lower bounds for finding stationary points II: first-order methods.
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford.
In Math. Program., vol. 185, no. 1-2, pp. 315-355, 2021.

BiB
TeX
Beyond Laurel/Yanny: An Autoencoder-Enabled Search for Polyperceivable Audio.
Kartik Chandra, Chuma Kabaghe, Gregory Valiant.
In proc. ACL/IJCNLP (2), pp. 593-598, 2021.

BiB
TeX
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity.
Moses Charikar, Weiyun Ma, Li-Yang Tan.
In proc. PODC, pp. 431-433, 2021.

BiB
TeX
Approximation Algorithms for Orthogonal Non-negative Matrix Factorization.
Moses Charikar, Lunjia Hu.
In proc. AISTATS, pp. 2728-2736, 2021.

BiB
TeX
A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract).
Moses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur.
In proc. ITCS, pp. 85:1-85:2, 2021.

BiB
TeX
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity.
Moses Charikar, Weiyun Ma, Li-Yang Tan.
In proc. PODC, pp. 431-433, 2021.

BiB
TeX
Improved Algorithms for Edge Colouring in the W-Streaming Model.
Moses Charikar, Paul Liu.
In proc. SOSA, pp. 181-183, 2021.

BiB
TeX
Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence.
Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, Yu Zheng.
In proc. ICALP, pp. 54:1-54:20, 2021.

BiB
TeX
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration.
Michael B. Cohen, Aaron Sidford, Kevin Tian.
In proc. ITCS, pp. 62:1-62:18, 2021.

BiB
TeX
Pseudorandom Generators for Read-Once Monotone Branching Programs.
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan.
In proc. APPROX-RANDOM, pp. 58:1-58:21, 2021.

BiB
TeX
Outcome indistinguishability.
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona.
In proc. STOC, pp. 1095-1108, 2021.

BiB
TeX
Express: Lowering the Cost of Metadata-hiding Communication with Cryptographic Privacy.
Saba Eskandarian, Henry Corrigan-Gibbs, Matei Zaharia, Dan Boneh.
In proc. USENIX Security Symposium, pp. 1775-1792, 2021.

BiB
TeX
Two-stage Stochastic Matching with Application to Ride Hailing.
Yiding Feng, Rad Niazadeh, Amin Saberi.
In proc. SODA, pp. 2862-2877, 2021.

BiB
TeX
On the Power and Limitations of Branch and Cut.
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson.
In proc. CCC, pp. 6:1-6:30, 2021.

BiB
TeX
Weighted Matrix Completion From Non-Random, Non-Uniform Sampling Patterns.
Simon Foucart, Deanna Needell, Reese Pathak, Yaniv Plan, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 67, no. 2, pp. 1264-1290, 2021.

BiB
TeX
Markets for public decision-making.
Nikhil Garg, Ashish Goel, Benjamin Plaut.
In Soc. Choice Welf., vol. 56, no. 4, pp. 755-801, 2021.

BiB
TeX
Approximate Gradient Coding with Optimal Decoding.
Margalit Glasgow, Mary Wootters.
In proc. ISIT, pp. 2280-2285, 2021.

BiB
TeX
Approximate Gradient Coding With Optimal Decoding.
Margalit Glasgow, Mary Wootters.
In IEEE J. Sel. Areas Inf. Theory, vol. 2, no. 3, pp. 855-866, 2021.

BiB
TeX
Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract].
Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters.
In proc. FOCS, pp. 708-719, 2021.

BiB
TeX
Sharp Threshold Rates for Random Codes.
Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters.
In proc. ITCS, pp. 5:1-5:20, 2021.

BiB
TeX
Wedge-Lifted Codes.
Jabari Hastings, Amy Kanne, Ray Li, Mary Wootters.
In proc. ISIT, pp. 2990-2995, 2021.

BiB
TeX
Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers.
Lunjia Hu, Omer Reingold.
In proc. AISTATS, pp. 1558-1566, 2021.

BiB
TeX
On Coding for an Abstracted Nanopore Channel for DNA Storage.
Reyna Hulett, Shubham Chandak, Mary Wootters.
In proc. ISIT, pp. 2465-2470, 2021.

BiB
TeX
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers.
Arun Jambulapati, Aaron Sidford.
In proc. SODA, pp. 540-559, 2021.

BiB
TeX
Decentralized Matching in a Probabilistic Environment.
Mobin Y. Jeloudar, Irene Lo, Tristan Pollner, Amin Saberi.
In proc. EC, pp. 635-653, 2021.

BiB
TeX
Towards Tight Bounds on the Sample Complexity of Average-reward MDPs.
Yujia Jin, Aaron Sidford.
In proc. ICML, pp. 5055-5064, 2021.

BiB
TeX
Sharper bounds on the Fourier concentration of DNFs.
Victor Lecomte, Li-Yang Tan.
In proc. FOCS, pp. 930-941, 2021.

BiB
TeX
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations.
Wenzheng Li, Jan Vondrák.
In proc. FOCS, pp. 25-36, 2021.

BiB
TeX
Estimating the Nash Social Welfare for coverage and other submodular valuations.
Wenzheng Li, Jan Vondrák.
In proc. SODA, pp. 1119-1130, 2021.

BiB
TeX
Lifted Multiplicity Codes and the Disjoint Repair Group Property.
Ray Li, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 67, no. 2, pp. 716-725, 2021.

BiB
TeX
Improved List-Decodability of Random Linear Binary Codes.
Ray Li, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 67, no. 3, pp. 1522-1536, 2021.

BiB
TeX
Cardinality constrained submodular maximization for random streams.
Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao.
In proc. NeurIPS, pp. 6491-6502, 2021.

BiB
TeX
Hermitian-lifted codes.
Hiram H. López, Beth Malmskog, Gretchen L. Matthews, Fernando Piñero-González, Mary Wootters.
In Des. Codes Cryptogr., vol. 89, no. 3, pp. 497-515, 2021.

BiB
TeX
The Strongish Planted Clique Hypothesis and Its Consequences.
Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm.
In proc. ITCS, pp. 10:1-10:21, 2021.

BiB
TeX
Misspecification in Prediction Problems and Robustness via Improper Learning.
Annie Marsden, John C. Duchi, Gregory Valiant.
In proc. AISTATS, pp. 2161-2169, 2021.

BiB
TeX
Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan.
In SIAM J. Comput., vol. 50, no. 6, pp. 1892-1922, 2021.

BiB
TeX
Deterministic Approximation of Random Walks in Small Space.
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan.
In Theory Comput., vol. 17, pp. 1-35, 2021.

BiB
TeX
Learning Multimodal Rewards from Rankings.
Vivek Myers, Erdem Biyik, Nima Anari, Dorsa Sadigh.
In proc. CoRL, pp. 342-352, 2021.

BiB
TeX
Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities.
Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, David Wajc.
In proc. EC, pp. 763-764, 2021.

BiB
TeX
Secure Complaint-Enabled Source-Tracking for Encrypted Messaging.
Charlotte Peale, Saba Eskandarian, Dan Boneh.
In proc. CCS, pp. 1484-1506, 2021.

BiB
TeX
Tradeoffs for small-depth Frege proofs.
Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan.
In proc. FOCS, pp. 445-456, 2021.

BiB
TeX
On Greedy Approaches to Hierarchical Aggregation.
Alexandra M. Porter, Mary Wootters.
In proc. ISIT, pp. 2649-2654, 2021.

BiB
TeX
Embedded Index Coding.
Alexandra M. Porter, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 67, no. 3, pp. 1461-1477, 2021.

BiB
TeX
Exponential Weights Algorithms for Selective Learning.
Mingda Qiao, Gregory Valiant.
In proc. COLT, pp. 3833-3858, 2021.

BiB
TeX
Stronger calibration lower bounds via sidestepping.
Mingda Qiao, Gregory Valiant.
In proc. STOC, pp. 456-466, 2021.

BiB
TeX
Constant-Round Interactive Proofs for Delegating Computation.
Omer Reingold, Guy N. Rothblum, Ron D. Rothblum.
In SIAM J. Comput., vol. 50, no. 3, 2021.

BiB
TeX
Linear-Time Erasure List-Decoding of Expander Codes.
Noga Ron-Zewi, Mary Wootters, Gilles Zémor.
In IEEE Trans. Inf. Theory, vol. 67, no. 9, pp. 5827-5839, 2021.

BiB
TeX
Exponential communication separations between notions of selfishness.
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao.
In proc. STOC, pp. 947-960, 2021.

BiB
TeX
The randomized communication complexity of randomized auctions.
Aviad Rubinstein, Junyao Zhao.
In proc. STOC, pp. 882-895, 2021.

BiB
TeX
The randomized communication complexity of revenue maximization.
Aviad Rubinstein, Junyao Zhao.
In SIGecom Exch., vol. 19, no. 2, pp. 75-83, 2021.

BiB
TeX
The Greedy Algorithm Is not Optimal for On-Line Edge Coloring.
Amin Saberi, David Wajc.
In proc. ICALP, pp. 109:1-109:18, 2021.

BiB
TeX
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma.
Rocco A. Servedio, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 37:1-37:18, 2021.

BiB
TeX
Robust Allocations with Diversity Constraints.
Zeyu Shen, Lodewijk Gelauff, Ashish Goel, Aleksandra Korolova, Kamesh Munagala.
In proc. NeurIPS, pp. 29684-29696, 2021.

BiB
TeX
Attacks on Onion Discovery and Remedies via Self-Authenticating Traditional Addresses.
Paul Syverson, Matthew Finkel, Saba Eskandarian, Dan Boneh.
In proc. WPES@CCS, pp. 45-52, 2021.

BiB
TeX
Sinkhorn Label Allocation: Semi-Supervised Classification via Annealed Self-Training.
Kai Sheng Tai, Peter Bailis, Gregory Valiant.
In proc. ICML, pp. 10065-10075, 2021.

BiB
TeX
SoK: Hate, Harassment, and the Changing Landscape of Online Abuse.
Kurt Thomas, Devdatta Akhawe, Michael D. Bailey, Dan Boneh, Elie Bursztein, Sunny Consolvo, Nicola Dell, Zakir Durumeric, Patrick Gage Kelley, Deepak Kumar, Damon McCoy, Sarah Meiklejohn, Thomas Ristenpart, Gianluca Stringhini.
In proc. SP, pp. 247-267, 2021.

BiB
TeX
Structured Robust Submodular Maximization: Offline and Online Algorithms.
Alfredo Torrico, Mohit Singh, Sebastian Pokutta, Nika Haghtalab, Joseph (Seffi) Naor, Nima Anari.
In INFORMS J. Comput., vol. 33, no. 4, pp. 1590-1607, 2021.

BiB
TeX
Differentially Private Learning Needs Better Features (or Much More Data).
Florian Tramèr, Dan Boneh.
In proc. ICLR, 2021.
2020

BiB
TeX
Leverage Score Sampling for Faster Accelerated Regression and ERM.
Naman Agarwal, Sham M. Kakade, Rahul Kidambi, Yin Tat Lee, Praneeth Netrapalli, Aaron Sidford.
In proc. ALT, pp. 22-47, 2020.

BiB
TeX
High-precision Estimation of Random Walks in Small Space.
AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, Salil P. Vadhan.
In proc. FOCS, pp. 1295-1306, 2020.

BiB
TeX
Instance Based Approximations to Profile Maximum Likelihood.
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. NeurIPS, 2020.

BiB
TeX
An Extension of Plücker Relations with Applications to Subdeterminant Maximization.
Nima Anari, Thuy-Duong Vuong.
In proc. APPROX-RANDOM, pp. 56:1-56:16, 2020.

BiB
TeX
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases.
Nima Anari, Michal Derezinski.
In proc. FOCS, pp. 1331-1344, 2020.

BiB
TeX
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model.
Nima Anari, Kuikui Liu, Shayan Oveis Gharan.
In proc. FOCS, pp. 1319-1330, 2020.

BiB
TeX
Matching Is as Easy as the Decision Problem, in the NC Model.
Nima Anari, Vijay V. Vazirani.
In proc. ITCS, pp. 54:1-54:25, 2020.

BiB
TeX
Instance Based Approximations to Profile Maximum Likelihood.
Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. NeurIPS, 2020.

BiB
TeX
Planar Graph Perfect Matching Is in NC.
Nima Anari, Vijay V. Vazirani.
In J. ACM, vol. 67, no. 4, pp. 21:1-21:34, 2020.

BiB
TeX
Queue Lengths as Constantly Adapting Prices: Allocative Efficiency Under Random Dynamics.
Itai Ashlagi, Jacob D. Leshno, Pengyu Qian, Amin Saberi.
In proc. EC, pp. 317-318, 2020.

BiB
TeX
Assignment Mechanisms Under Distributional Constraints.
Itai Ashlagi, Amin Saberi, Ali Shameli.
In Oper. Res., vol. 68, no. 2, pp. 467-479, 2020.

BiB
TeX
Sample Amplification: Increasing Dataset Size even when Learning is Impossible.
Brian Axelrod, Shivam Garg, Vatsal Sharan, Gregory Valiant.
In proc. ICML, pp. 442-451, 2020.

BiB
TeX
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization.
Brian Axelrod, Yang P. Liu, Aaron Sidford.
In proc. SODA, pp. 837-853, 2020.

BiB
TeX
Communication complexity of Nash equilibrium in potential games (extended abstract).
Yakov Babichenko, Aviad Rubinstein.
In proc. FOCS, pp. 1439-1445, 2020.

BiB
TeX
Submodular Maximization Through Barrier Functions.
Ashwinkumar Badanidiyuru, Amin Karbasi, Ehsan Kazemi, Jan Vondrák.
In proc. NeurIPS, 2020.

BiB
TeX
Non-malleability Against Polynomial Tampering.
Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan.
In proc. CRYPTO (3), pp. 97-126, 2020.

BiB
TeX
The Power of Many Samples in Query Complexity.
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan.
In proc. ICALP, pp. 9:1-9:18, 2020.

BiB
TeX
Stochastic Gradient Coding for Straggler Mitigation in Distributed Learning.
Rawad Bitar, Mary Wootters, Salim El Rouayheb.
In IEEE J. Sel. Areas Inf. Theory, vol. 1, no. 1, pp. 277-291, 2020.

BiB
TeX
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process.
Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant.
In proc. COLT, pp. 483-513, 2020.

BiB
TeX
Provable guarantees for decision tree induction: the agnostic setting.
Guy Blanc, Jane Lange, Li-Yang Tan.
In proc. ICML, pp. 941-949, 2020.

BiB
TeX
Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations.
Guy Blanc, Jane Lange, Li-Yang Tan.
In proc. ITCS, pp. 44:1-44:44, 2020.

BiB
TeX
Estimating decision tree learnability with polylogarithmic sample complexity.
Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan.
In proc. NeurIPS, 2020.

BiB
TeX
Universal guarantees for decision tree induction via a higher-order splitting criterion.
Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan.
In proc. NeurIPS, 2020.

BiB
TeX
Single Secret Leader Election.
Dan Boneh, Saba Eskandarian, Lucjan Hanzlik, Nicola Greco.
In proc. AFT, pp. 12-24, 2020.

BiB
TeX
Improving Speed and Security in Updatable Encryption Schemes.
Dan Boneh, Saba Eskandarian, Sam Kim, Maurice Shih.
In proc. ASIACRYPT (3), pp. 559-589, 2020.

BiB
TeX
Oblivious Pseudorandom Functions from Isogenies.
Dan Boneh, Dmitry Kogan, Katharine Woo.
In proc. ASIACRYPT (2), pp. 520-550, 2020.

BiB
TeX
Multiparty Non-Interactive Key Exchange and More From Isogenies on Elliptic Curves.
Dan Boneh, Darren B. Glass, Daniel Krashen, Kristin E. Lauter, Shahed Sharif, Alice Silverberg, Mehdi Tibouchi, Mark Zhandry.
In J. Math. Cryptol., vol. 14, no. 1, pp. 5-14, 2020.

BiB
TeX
Smoothed Complexity of 2-player Nash Equilibria.
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein.
In proc. FOCS, pp. 271-282, 2020.

BiB
TeX
Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract).
Adam Bouland, Bill Fefferman, Umesh V. Vazirani.
In proc. ITCS, pp. 63:1-63:2, 2020.

BiB
TeX
On the Power of Statistical Zero Knowledge.
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan.
In SIAM J. Comput., vol. 49, no. 4, 2020.

BiB
TeX
Constant-factor approximation of near-linear edit distance in near-linear time.
Joshua Brakensiek, Aviad Rubinstein.
In proc. STOC, pp. 685-698, 2020.

BiB
TeX
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang.
In proc. FOCS, pp. 919-930, 2020.

BiB
TeX
Solving tall dense linear programs in nearly linear time.
Jan van den Brand, Yin Tat Lee, Aaron Sidford, Zhao Song.
In proc. STOC, pp. 775-788, 2020.

BiB
TeX
The one-way communication complexity of dynamic time warping distance.
Vladimir Braverman, Moses Charikar, William Kuszmaul, Lin F. Yang.
In J. Comput. Geom., vol. 11, no. 2, pp. 62-93, 2020.

BiB
TeX
Zether: Towards Privacy in a Smart Contract World.
Benedikt Bünz, Shashank Agrawal, Mahdi Zamani, Dan Boneh.
In proc. Financial Cryptography, pp. 423-443, 2020.

BiB
TeX
Coordinate Methods for Matrix Games.
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian.
In proc. FOCS, pp. 283-293, 2020.

BiB
TeX
Acceleration with a Ball Optimization Oracle.
Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, Kevin Tian.
In proc. NeurIPS, 2020.

BiB
TeX
Lower bounds for finding stationary points I.
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford.
In Math. Program., vol. 184, no. 1, pp. 71-120, 2020.

BiB
TeX
Overcoming High Nanopore Basecaller Error Rates for DNA Storage via Basecaller-Decoder Integration and Convolutional Codes.
Shubham Chandak, Joachim Neu, Kedar Tatwawadi, Jay Mardia, Billy Lau, Matthew Kubit, Reyna Hulett, Peter Griffin, Mary Wootters, Tsachy Weissman, Hanlee Ji.
In proc. ICASSP, pp. 8822-8826, 2020.

BiB
TeX
Unconditional Lower Bounds for Adaptive Massively Parallel Computation.
Moses Charikar, Weiyun Ma, Li-Yang Tan.
In proc. SPAA, pp. 141-151, 2020.

BiB
TeX
Kernel Density Estimation through Density Constrained Near Neighbor Search.
Moses Charikar, Michael Kapralov, Navid Nouri, Paris Siminelakis.
In proc. FOCS, pp. 172-183, 2020.

BiB
TeX
Adaptive Discrete Phase Retrieval.
Moses Charikar, Xian Wu, Yinyu Ye.
In proc. SOSA, pp. 47-56, 2020.

BiB
TeX
Unconditional Lower Bounds for Adaptive Massively Parallel Computation.
Moses Charikar, Weiyun Ma, Li-Yang Tan.
In proc. SPAA, pp. 141-151, 2020.

BiB
TeX
Constant girth approximation for directed graphs in subquadratic time.
Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford.
In proc. STOC, pp. 1010-1023, 2020.

BiB
TeX
Worst-Case Analysis for Randomly Collected Data.
Justin Y. Chen, Gregory Valiant, Paul Valiant.
In proc. NeurIPS, 2020.

BiB
TeX
A Systematic Review of Smartphone Applications Available for Corona Virus Disease 2019 (COVID19) and the Assessment of their Quality Using the Mobile Application Rating Scale (MARS).
Samira Davalbhakta, Shailesh Advani, Shobhit Kumar, Vishwesh Agarwal, Samruddhi Bhoyar, Elizabeth Fedirko, Durga Prasanna Misra, Ashish Goel, Latika Gupta, Vikas Agarwal.
In J. Medical Syst., vol. 44, no. 9, pp. 164, 2020.

BiB
TeX
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria.
Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis.
In proc. ITCS, pp. 18:1-18:19, 2020.

BiB
TeX
Tight bounds on ℓ1 approximation and learning of self-bounding functions.
Vitaly Feldman, Pravesh Kothari, Jan Vondrák.
In Theor. Comput. Sci., vol. 808, pp. 86-98, 2020.

BiB
TeX
CoopStore: Optimizing Precomputed Summaries for Aggregation.
Edward Gan, Peter Bailis, Moses Charikar.
In Proc. VLDB Endow., vol. 13, no. 11, pp. 2174-2187, 2020.

BiB
TeX
Institutions Share Successes, Failures, and Advice in Moving the Diversity Needle.
Dan Garcia, Moses Charikar, Eboney Hearn, Ed Lazowska, Jonathan Reynolds.
In proc. SIGCSE, pp. 331-332, 2020.

BiB
TeX
Sparse Recovery for Orthogonal Polynomial Transforms.
Anna C. Gilbert, Albert Gu, Christopher Ré, Atri Rudra, Mary Wootters.
In proc. ICALP, pp. 58:1-58:16, 2020.

BiB
TeX
Continuous Credit Networks and Layer 2 Blockchains: Monotonicity and Sampling.
Ashish Goel, Geoffrey Ramseyer.
In proc. EC, pp. 613-635, 2020.

BiB
TeX
Counteracting Inequality in Markets via Convex Pricing.
Ashish Goel, Benjamin Plaut.
In proc. WINE, pp. 89-101, 2020.

BiB
TeX
Does preprocessing help in fast sequence comparisons?
Elazar Goldenberg, Aviad Rubinstein, Barna Saha.
In proc. STOC, pp. 657-670, 2020.

BiB
TeX
Bounds for List-Decoding and List-Recovery of Random Linear Codes.
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters.
In proc. APPROX-RANDOM, pp. 9:1-9:21, 2020.

BiB
TeX
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing.
Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil P. Vadhan, Hoeteck Wee.
In Theory Comput., vol. 16, pp. 1-55, 2020.

BiB
TeX
An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles.
Nicholas J. A. Harvey, Jan Vondrák.
In SIAM J. Comput., vol. 49, no. 2, pp. 394-428, 2020.

BiB
TeX
Local List Recovery of High-Rate Tensor Codes and Applications.
Brett Hemenway, Noga Ron-Zewi, Mary Wootters.
In SIAM J. Comput., vol. 49, no. 4, 2020.

BiB
TeX
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.
Oliver Hinder, Aaron Sidford, Nimit Sharad Sohoni.
In proc. COLT, pp. 1894-1938, 2020.

BiB
TeX
Efficiently Solving MDPs with Stochastic Mirror Descent.
Yujia Jin, Aaron Sidford.
In proc. ICML, pp. 4890-4900, 2020.

BiB
TeX
Fast and Space Efficient Spectral Sparsification in Dynamic Streams.
Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, Jakab Tardos.
In proc. SODA, pp. 1814-1833, 2020.

BiB
TeX
Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time.
Tarun Kathuria, Yang P. Liu, Aaron Sidford.
In proc. FOCS, pp. 119-130, 2020.

BiB
TeX
Sublinear Optimal Policy Value Estimation in Contextual Bandits.
Weihao Kong, Emma Brunskill, Gregory Valiant.
In proc. AISTATS, pp. 4377-4387, 2020.

BiB
TeX
Retrieving Top Weighted Triangles in Graphs.
Raunak Kumar, Paul Liu, Moses Charikar, Austin R. Benson.
In proc. WSDM, pp. 295-303, 2020.

BiB
TeX
Large-Scale Methods for Distributionally Robust Optimization.
Daniel Levy, Yair Carmon, John C. Duchi, Aaron Sidford.
In proc. NeurIPS, 2020.

BiB
TeX
A polynomial lower bound on adaptive complexity of submodular maximization.
Wenzheng Li, Paul Liu, Jan Vondrák.
In proc. STOC, pp. 140-152, 2020.

BiB
TeX
Bounded-Leakage Differential Privacy.
Katrina Ligett, Charlotte Peale, Omer Reingold.
In proc. FORC, pp. 10:1-10:20, 2020.

BiB
TeX
Faster energy maximization for faster maximum flow.
Yang P. Liu, Aaron Sidford.
In proc. STOC, pp. 803-814, 2020.

BiB
TeX
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics.
Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein.
In proc. NeurIPS, 2020.

BiB
TeX
LDPC Codes Achieve List Decoding Capacity.
Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters.
In proc. FOCS, pp. 458-469, 2020.

BiB
TeX
Fooling Gaussian PTFs via local hyperconcentration.
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 1170-1183, 2020.

BiB
TeX
Scaling Verifiable Computation Using Efficient Set Accumulators.
Alex Ozdemir, Riad S. Wahby, Barry Whitehat, Dan Boneh.
In proc. USENIX Security Symposium, pp. 2075-2092, 2020.

BiB
TeX
Online Hypergraph Matching with Delays.
Marco Pavone, Amin Saberi, Maximilian Schiffer, Matthew Tsao.
In proc. WINE, pp. 465, 2020.

BiB
TeX
Liquidity in Credit Networks with Constrained Agents.
Geoffrey Ramseyer, Ashish Goel, David Mazières.
In proc. WWW, pp. 2099-2108, 2020.

BiB
TeX
Satellite Navigation for the Age of Autonomy.
Tyler G. R. Reid, Bryan Chan, Ashish Goel, Kazuma Gunning, Brian Manning, Jerami Martin, Andrew Neish, Adrien Perkins, Paul M. Tarantino.
In proc. PLANS, pp. 342-352, 2020.

BiB
TeX
Through the lens of a passionate theoretician.
Omer Reingold.
In Commun. ACM, vol. 63, no. 3, pp. 25-27, 2020.

BiB
TeX
Linear-time Erasure List-decoding of Expander Codes.
Noga Ron-Zewi, Mary Wootters, Gilles Zémor.
In proc. ISIT, pp. 379-383, 2020.

BiB
TeX
Optimal Single-Choice Prophet Inequalities from Samples.
Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg.
In proc. ITCS, pp. 60:1-60:10, 2020.

BiB
TeX
Reducing approximate Longest Common Subsequence to approximate Edit Distance.
Aviad Rubinstein, Zhao Song.
In proc. SODA, pp. 1591-1600, 2020.

BiB
TeX
The impossibility of low-rank representations for triangle-rich complex networks.
C. Seshadhri, Aneesh Sharma, Andrew Stolman, Ashish Goel.
In Proc. Natl. Acad. Sci. USA, vol. 117, no. 11, pp. 5631-5637, 2020.

BiB
TeX
Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise.
Noah Shutty, Mary Wootters, Patrick Hayden.
In proc. FOCS, pp. 206-217, 2020.

BiB
TeX
Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity.
Aaron Sidford, Mengdi Wang, Lin Yang, Yinyu Ye.
In proc. AISTATS, pp. 2992-3002, 2020.

BiB
TeX
Remote Side-Channel Attacks on Anonymous Transactions.
Florian Tramèr, Dan Boneh, Kenny Paterson.
In proc. USENIX Security Symposium, pp. 2739-2756, 2020.

BiB
TeX
An Airdrop that Preserves Recipient Privacy.
Riad S. Wahby, Dan Boneh, Christopher Jeffrey, Joseph Poon.
In proc. Financial Cryptography, pp. 444-463, 2020.

BiB
TeX
List-Decodability of Structured Ensembles of Codes (Invited Talk).
Mary Wootters.
In proc. MFCS, pp. 3:1-3:5, 2020.

BiB
TeX
On the Generalization Effects of Linear Transformations in Data Augmentation.
Sen Wu, Hongyang R. Zhang, Gregory Valiant, Christopher Ré.
In proc. ICML, pp. 10410-10420, 2020.
2019

BiB
TeX
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications.
AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford.
In proc. SODA, pp. 1387-1404, 2019.

BiB
TeX
Competition in Ride-Hailing Markets.
AmirMahdi Ahmadinejad, Hamid Nazerzadeh, Amin Saberi, Nolan Skochdopole, Kane Sweeney.
In proc. WINE, pp. 333, 2019.

BiB
TeX
The N3XT Approach to Energy-Efficient Abundant-Data Computing.
Mohamed M. Sabry Aly, Tony F. Wu, Andrew Bartolo, Yash H. Malviya, William Hwang, Gage Hills, Igor L. Markov, Mary Wootters, Max M. Shulaker, H.-S. Philip Wong, Subhasish Mitra.
In Proc. IEEE, vol. 107, no. 1, pp. 19-48, 2019.

BiB
TeX
Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection.
Nima Anari, Rad Niazadeh, Amin Saberi, Ali Shameli.
In proc. EC, pp. 91-92, 2019.

BiB
TeX
Structured Robust Submodular Maximization: Offline and Online Algorithms.
Nima Anari, Nika Haghtalab, Seffi Naor, Sebastian Pokutta, Mohit Singh, Alfredo Torrico.
In proc. AISTATS, pp. 3128-3137, 2019.

BiB
TeX
Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection.
Nima Anari, Rad Niazadeh, Amin Saberi, Ali Shameli.
In proc. EC, pp. 91-92, 2019.

BiB
TeX
A Tight Analysis of Bethe Approximation for Permanent.
Nima Anari, Alireza Rezaei.
In proc. FOCS, pp. 1434-1445, 2019.

BiB
TeX
Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid.
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant.
In proc. STOC, pp. 1-12, 2019.

BiB
TeX
Edge Weighted Online Windowed Matching.
Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, Chris Sholley.
In proc. EC, pp. 729-742, 2019.

BiB
TeX
Assignment Mechanisms under Distributional Constraints.
Itai Ashlagi, Amin Saberi, Ali Shameli.
In proc. SODA, pp. 229-240, 2019.

BiB
TeX
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families.
Brian Axelrod, Ilias Diakonikolas, Alistair Stewart, Anastasios Sidiropoulos, Gregory Valiant.
In proc. NeurIPS, pp. 7721-7733, 2019.

BiB
TeX
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation.
Eric Balkanski, Aviad Rubinstein, Yaron Singer.
In proc. SODA, pp. 283-302, 2019.

BiB
TeX
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model.
Eric Balkanski, Aviad Rubinstein, Yaron Singer.
In proc. STOC, pp. 66-77, 2019.

BiB
TeX
Reductions in PPP.
Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, Aviad Rubinstein.
In Inf. Process. Lett., vol. 145, pp. 48-52, 2019.

BiB
TeX
Stochastic Gradient Coding for Flexible Straggler Mitigation in Distributed Learning.
Rawad Bitar, Mary Wootters, Salim El Rouayheb.
In proc. ITW, pp. 1-5, 2019.

BiB
TeX
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs.
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai.
In proc. CRYPTO (3), pp. 67-97, 2019.

BiB
TeX
Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains.
Dan Boneh, Benedikt Bünz, Ben Fisch.
In proc. CRYPTO (1), pp. 561-586, 2019.

BiB
TeX
Post-quantum EPID Signatures from Symmetric Primitives.
Dan Boneh, Saba Eskandarian, Ben Fisch.
In proc. CT-RSA, pp. 251-271, 2019.

BiB
TeX
Technical perspective: Attacking cryptographic key exchange with precomputation.
Dan Boneh.
In Commun. ACM, vol. 62, no. 1, pp. 105, 2019.

BiB
TeX
How Relevant Is the Turing Test in the Age of Sophisbots?
Dan Boneh, Andrew J. Grotto, Patrick D. McDaniel, Nicolas Papernot.
In IEEE Secur. Priv., vol. 17, no. 6, pp. 64-71, 2019.

BiB
TeX
"Quantum Supremacy" and the Complexity of Random Circuit Sampling.
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani.
In proc. ITCS, pp. 15:1-15:2, 2019.

BiB
TeX
The One-Way Communication Complexity of Dynamic Time Warping Distance.
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang.
In proc. SoCG, pp. 16:1-16:15, 2019.

BiB
TeX
Near-optimal method for highly smooth convex optimization.
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford.
In proc. COLT, pp. 492-507, 2019.

BiB
TeX
Complexity of Highly Parallel Non-Smooth Convex Optimization.
Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford.
In proc. NeurIPS, pp. 13900-13909, 2019.

BiB
TeX
A Rank-1 Sketch for Matrix Multiplicative Weights.
Yair Carmon, John C. Duchi, Aaron Sidford, Kevin Tian.
In proc. COLT, pp. 589-623, 2019.

BiB
TeX
Variance Reduction for Matrix Games.
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian.
In proc. NeurIPS, pp. 11377-11388, 2019.

BiB
TeX
Faster Matroid Intersection.
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong.
In proc. FOCS, pp. 1146-1168, 2019.

BiB
TeX
Improved read/write cost tradeoff in DNA-based data storage using LDPC codes.
Shubham Chandak, Hanlee Ji, Kedar Tatwawadi, Billy Lau, Jay Mardia, Matthew Kubit, Joachim Neu, Peter Griffin, Mary Wootters, Tsachy Weissman.
In proc. Allerton, pp. 147-156, 2019.

BiB
TeX
A General Framework for Symmetric Property Estimation.
Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. NeurIPS, pp. 12426-12436, 2019.

BiB
TeX
Efficient profile maximum likelihood for universal symmetric property estimation.
Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. STOC, pp. 780-791, 2019.

BiB
TeX
Hierarchical Clustering for Euclidean Data.
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev.
In proc. AISTATS, pp. 2721-2730, 2019.

BiB
TeX
Multi-resolution Hashing for Fast Pairwise Summations.
Moses Charikar, Paris Siminelakis.
In proc. FOCS, pp. 769-792, 2019.

BiB
TeX
A General Framework for Symmetric Property Estimation.
Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. NeurIPS, pp. 12426-12436, 2019.

BiB
TeX
Hierarchical Clustering better than Average-Linkage.
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh.
In proc. SODA, pp. 2291-2304, 2019.

BiB
TeX
Efficient profile maximum likelihood for universal symmetric property estimation.
Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. STOC, pp. 780-791, 2019.

BiB
TeX
Fine-grained Complexity Meets IP = PSPACE.
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein.
In proc. SODA, pp. 1-20, 2019.

BiB
TeX
True2F: Backdoor-Resistant Authentication Tokens.
Emma Dauterman, Henry Corrigan-Gibbs, David Mazières, Dan Boneh, Dominic Rizzo.
In proc. IEEE Symposium on Security and Privacy, pp. 398-416, 2019.

BiB
TeX
Blind Joint MIMO Channel Estimation and Decoding.
Thomas R. Dean, Mary Wootters, Andrea J. Goldsmith.
In IEEE Trans. Inf. Theory, vol. 65, no. 4, pp. 2507-2524, 2019.

BiB
TeX
Fast Blind MIMO Decoding Through Vertex Hopping.
Thomas R. Dean, Jonathan Perlstein, Mary Wootters, Andrea J. Goldsmith.
In IEEE Trans. Wirel. Commun., vol. 18, no. 7, pp. 3669-3682, 2019.

BiB
TeX
Learning from Outcomes: Evidence-Based Rankings.
Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona.
In proc. FOCS, pp. 106-125, 2019.

BiB
TeX
Fidelius: Protecting User Secrets from Compromised Browsers.
Saba Eskandarian, Jonathan Cogan, Sawyer Birnbaum, Peh Chang Wei Brandon, Dillon Franke, Forest Fraser, Gaspar Garcia Jr., Eric Gong, Hung T. Nguyen, Taresh K. Sethi, Vishal Subbiah, Michael Backes, Giancarlo Pellegrino, Dan Boneh.
In proc. IEEE Symposium on Security and Privacy, pp. 264-280, 2019.

BiB
TeX
Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice.
Brandon Fain, Ashish Goel, Kamesh Munagala, Nina Prabhu.
In proc. AAAI, pp. 1893-1900, 2019.

BiB
TeX
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.
Vitaly Feldman, Jan Vondrák.
In proc. COLT, pp. 1270-1279, 2019.

BiB
TeX
Tracking and Improving Information in the Service of Fairness.
Sumegha Garg, Michael P. Kim, Omer Reingold.
In proc. EC, pp. 809-824, 2019.

BiB
TeX
Who Is in Your Top Three? Optimizing Learning in Elections with Many Candidates.
Nikhil Garg, Lodewijk Gelauff, Sukolsak Sakshuwong, Ashish Goel.
In proc. HCOMP, pp. 22-31, 2019.

BiB
TeX
Iterative Local Voting for Collective Decision-making in Continuous Spaces.
Nikhil Garg, Vijay Kamble, Ashish Goel, David Marn, Kamesh Munagala.
In J. Artif. Intell. Res., vol. 64, pp. 315-355, 2019.

BiB
TeX
Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives.
Alexander V. Gasnikov, Pavel E. Dvurechensky, Eduard Gorbunov, Evgeniya A. Vorontsova, Daniil Selikhanovych, César A. Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, Aaron Sidford.
In proc. COLT, pp. 1392-1393, 2019.

BiB
TeX
Making AI Forget You: Data Deletion in Machine Learning.
Antonio Ginart, Melody Y. Guan, Gregory Valiant, James Zou.
In proc. NeurIPS, pp. 3513-3526, 2019.

BiB
TeX
Markets Beyond Nash Welfare for Leontief Utilities.
Ashish Goel, Reyna Hulett, Benjamin Plaut.
In proc. WINE, pp. 340, 2019.

BiB
TeX
Perfect Matchings in Õ (n 1.5) Time in Regular Bipartite Graphs.
Ashish Goel, Michael Kapralov, Sanjeev Khanna.
In Comb., vol. 39, no. 2, pp. 323-354, 2019.

BiB
TeX
A novel quadrilateral companding transform for PAPR reduction in OFDM systems.
Ashish Goel, Prerana Gupta Poddar, Monika Agrawal.
In Digit. Signal Process., vol. 85, pp. 113-123, 2019.

BiB
TeX
Knapsack Voting for Participatory Budgeting.
Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong, Tanja Aitamurto.
In ACM Trans. Economics and Comput., vol. 7, no. 2, pp. 8:1-8:27, 2019.

BiB
TeX
A Surprising Density of Illusionable Natural Speech.
Melody Y. Guan, Gregory Valiant.
In proc. CogSci, pp. 1871, 2019.

BiB
TeX
Near-linear time insertion-deletion codes and (1+ε)-approximating edit distance via indexing.
Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi.
In proc. STOC, pp. 697-708, 2019.

BiB
TeX
On the Communication Complexity of Key-Agreement Protocols.
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff.
In proc. ITCS, pp. 40:1-40:16, 2019.

BiB
TeX
On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing.
Huseyin A. Inan, Peter Kairouz, Mary Wootters, Ayfer Özgür.
In IEEE Trans. Inf. Theory, vol. 65, no. 9, pp. 5592-5603, 2019.

BiB
TeX
A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport.
Arun Jambulapati, Aaron Sidford, Kevin Tian.
In proc. NeurIPS, pp. 11355-11366, 2019.

BiB
TeX
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG.
Yujia Jin, Aaron Sidford.
In proc. NeurIPS, pp. 3863-3873, 2019.

BiB
TeX
Falcon - A Flexible Architecture For Accelerating Cryptography.
Kevin Kiningham, Philip Alexander Levis, Mark Anderson, Dan Boneh, Mark Horowitz, Maurice Shih.
In proc. MASS, pp. 136-144, 2019.

BiB
TeX
Lifted Multiplicity Codes and the Disjoint Repair Group Property.
Ray Li, Mary Wootters.
In proc. APPROX-RANDOM, pp. 38:1-38:18, 2019.

BiB
TeX
Parallel Reachability in Almost Linear Work and Square Root Depth.
Yang P. Liu, Arun Jambulapati, Aaron Sidford.
In proc. FOCS, pp. 1664-1686, 2019.

BiB
TeX
Submodular Optimization in the MapReduce Model.
Paul Liu, Jan Vondrák.
In proc. SOSA, pp. 18:1-18:10, 2019.

BiB
TeX
Sampling Methods for Counting Temporal Motifs.
Paul Liu, Austin R. Benson, Moses Charikar.
In proc. WSDM, pp. 294-302, 2019.

BiB
TeX
Repairing Multiple Failures for Scalar MDS Codes.
Jay Mardia, Burak Bartan, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 65, no. 5, pp. 2661-2672, 2019.

BiB
TeX
Pseudorandom generators for width-3 branching programs.
Raghu Meka, Omer Reingold, Avishay Tal.
In proc. STOC, pp. 626-637, 2019.

BiB
TeX
A Data-Compressive Wired-OR Readout for Massively Parallel Neural Recording.
Dante G. Muratore, Pulkit Tandon, Mary Wootters, E. J. Chichilnisky, Subhasish Mitra, Boris Murmann.
In proc. ISCAS, pp. 1-5, 2019.

BiB
TeX
A Data-Compressive Wired-OR Readout for Massively Parallel Neural Recording.
Dante Gabriel Muratore, Pulkit Tandon, Mary Wootters, E. J. Chichilnisky, Subhasish Mitra, Boris Murmann.
In IEEE Trans. Biomed. Circuits Syst., vol. 13, no. 6, pp. 1128-1140, 2019.

BiB
TeX
Deterministic Approximation of Random Walks in Small Space.
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan.
In proc. APPROX-RANDOM, pp. 42:1-42:22, 2019.

BiB
TeX
Fooling polytopes.
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 614-625, 2019.

BiB
TeX
Embedded Index Coding.
Alexandra M. Porter, Mary Wootters.
In proc. ITW, pp. 1-5, 2019.

BiB
TeX
A Theory of Selective Prediction.
Mingda Qiao, Gregory Valiant.
In proc. COLT, pp. 2580-2594, 2019.

BiB
TeX
Hardness of Approximation Between P and NP
Aviad Rubinstein.
Published by ACM, 2019, isbn 978-1-94748-723-9.

BiB
TeX
Approximation Algorithms for LCS and LIS with Truly Improved Running Times.
Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun.
In proc. FOCS, pp. 1121-1145, 2019.

BiB
TeX
SETH vs Approximation.
Aviad Rubinstein, Virginia Vassilevska Williams.
In SIGACT News, vol. 50, no. 4, pp. 57-76, 2019.

BiB
TeX
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas.
Rocco A. Servedio, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 45:1-45:23, 2019.

BiB
TeX
Pseudorandomness for read-k DNF formulas.
Rocco A. Servedio, Li-Yang Tan.
In proc. SODA, pp. 621-638, 2019.

BiB
TeX
Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data.
Vatsal Sharan, Kai Sheng Tai, Peter Bailis, Gregory Valiant.
In proc. ICML, pp. 5690-5700, 2019.

BiB
TeX
Memory-sample tradeoffs for linear regression with small error.
Vatsal Sharan, Aaron Sidford, Gregory Valiant.
In proc. STOC, pp. 890-901, 2019.

BiB
TeX
Rehashing Kernel Evaluation in High Dimensions.
Paris Siminelakis, Kexin Rong, Peter Bailis, Moses Charikar, Philip Alexander Levis.
In proc. ICML, pp. 5789-5798, 2019.

BiB
TeX
Unconstraining Graph-Constrained Group Testing.
Bruce Spang, Mary Wootters.
In proc. APPROX-RANDOM, pp. 46:1-46:20, 2019.

BiB
TeX
Equivariant Transformer Networks.
Kai Sheng Tai, Peter Bailis, Gregory Valiant.
In proc. ICML, pp. 6086-6095, 2019.

BiB
TeX
Protecting accounts from credential stuffing with password breach alerting.
Kurt Thomas, Jennifer Pullman, Kevin Yeo, Ananth Raghunathan, Patrick Gage Kelley, Luca Invernizzi, Borbala Benko, Tadek Pietraszek, Sarvar Patel, Dan Boneh, Elie Bursztein.
In proc. USENIX Security Symposium, pp. 1556-1571, 2019.

BiB
TeX
AdVersarial: Perceptual Ad Blocking meets Adversarial Machine Learning.
Florian Tramèr, Pascal Dupré, Gili Rusak, Giancarlo Pellegrino, Dan Boneh.
In proc. CCS, pp. 2005-2021, 2019.

BiB
TeX
Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware.
Florian Tramèr, Dan Boneh.
In proc. ICLR, 2019.

BiB
TeX
Adversarial Training and Robustness for Multiple Perturbations.
Florian Tramèr, Dan Boneh.
In proc. NeurIPS, pp. 5858-5868, 2019.

BiB
TeX
Maximum Likelihood Estimation for Learning Populations of Parameters.
Ramya Korlakai Vinayak, Weihao Kong, Gregory Valiant, Sham M. Kakade.
In proc. ICML, pp. 6448-6457, 2019.

BiB
TeX
Fast and simple constant-time hashing to the BLS12-381 elliptic curve.
Riad S. Wahby, Dan Boneh.
In IACR Trans. Cryptogr. Hardw. Embed. Syst., vol. 2019, no. 4, pp. 154-179, 2019.

BiB
TeX
A 43pJ/Cycle Non-Volatile Microcontroller with 4.7μs Shutdown/Wake-up Integrating 2.3-bit/Cell Resistive RAM and Resilience Techniques.
Tony F. Wu, Binh Q. Le, Robert M. Radway, Andrew Bartolo, William Hwang, Seungbin Jeong, Haitong Li, Pulkit Tandon, Elisa Vianello, Pascal Vivet, Etienne Nowak, Mary Wootters, H.-S. Philip Wong, Mohamed M. Sabry Aly, Edith Beigné, Subhasish Mitra.
In proc. ISSCC, pp. 226-228, 2019.

BiB
TeX
Recovery Guarantees For Quadratic Tensors With Sparse Observations.
Hongyang Zhang, Vatsal Sharan, Moses Charikar, Yingyu Liang.
In proc. AISTATS, pp. 3322-3332, 2019.

BiB
TeX
Pruning based Distance Sketches with Provable Guarantees on Random Graphs.
Hongyang Zhang, Huacheng Yu, Ashish Goel.
In proc. WWW, pp. 2301-2311, 2019.
2018

BiB
TeX
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds.
Amir Abboud, Aviad Rubinstein.
In proc. ITCS, pp. 35:1-35:14, 2018.

BiB
TeX
Diffusion, Seeding, and the Value of Network Information.
Mohammad Akbarpour, Suraj Malladi, Amin Saberi.
In proc. EC, pp. 641, 2018.

BiB
TeX
Graph Clustering using Effective Resistance.
Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan.
In proc. ITCS, pp. 41:1-41:16, 2018.

BiB
TeX
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons.
Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos H. Papadimitriou, Amin Saberi, Santosh S. Vempala.
In proc. NeurIPS, pp. 10880-10890, 2018.

BiB
TeX
Approximating the Largest Root and Applications to Interlacing Families.
Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava.
In proc. SODA, pp. 1015-1028, 2018.

BiB
TeX
Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids.
Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant.
In proc. FOCS, pp. 35-46, 2018.

BiB
TeX
Planar Graph Perfect Matching Is in NC.
Nima Anari, Vijay V. Vazirani.
In proc. FOCS, pp. 650-661, 2018.

BiB
TeX
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons.
Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos H. Papadimitriou, Amin Saberi, Santosh S. Vempala.
In proc. NeurIPS, pp. 10880-10890, 2018.

BiB
TeX
Approximating the Largest Root and Applications to Interlacing Families.
Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava.
In proc. SODA, pp. 1015-1028, 2018.

BiB
TeX
Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities.
Nima Anari, Tung Mai, Shayan Oveis Gharan, Vijay V. Vazirani.
In proc. SODA, pp. 2274-2290, 2018.

BiB
TeX
Budget Feasible Procurement Auctions.
Nima Anari, Gagan Goel, Afshin Nikzad.
In Oper. Res., vol. 66, no. 3, pp. 637-652, 2018.

BiB
TeX
Optimal Deterministic Mechanisms for an Additive Buyer.
Moshe Babaioff, Noam Nisan, Aviad Rubinstein.
In proc. EC, pp. 429, 2018.

BiB
TeX
Efficient Density Evaluation for Smooth Kernels.
Arturs Backurs, Moses Charikar, Piotr Indyk, Paris Siminelakis.
In proc. FOCS, pp. 615-626, 2018.

BiB
TeX
Non-Malleable Codes for Small-Depth Circuits.
Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan.
In proc. FOCS, pp. 826-837, 2018.

BiB
TeX
Generating Random Networks Without Short Cycles.
Mohsen Bayati, Andrea Montanari, Amin Saberi.
In Oper. Res., vol. 66, no. 5, pp. 1227-1246, 2018.

BiB
TeX
Classical Lower Bounds from Quantum Upper Bounds.
Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari.
In proc. FOCS, pp. 339-349, 2018.

BiB
TeX
Compact Multi-signatures for Smaller Blockchains.
Dan Boneh, Manu Drijvers, Gregory Neven.
In proc. ASIACRYPT (2), pp. 435-464, 2018.

BiB
TeX
Verifiable Delay Functions.
Dan Boneh, Joseph Bonneau, Benedikt Bünz, Ben Fisch.
In proc. CRYPTO (1), pp. 757-788, 2018.

BiB
TeX
Threshold Cryptosystems from Threshold Fully Homomorphic Encryption.
Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, Amit Sahai.
In proc. CRYPTO (1), pp. 565-596, 2018.

BiB
TeX
Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs.
Dan Boneh, Yuval Ishai, Amit Sahai, David J. Wu.
In proc. EUROCRYPT (3), pp. 222-255, 2018.

BiB
TeX
Exploring Crypto Dark Matter: - New Simple PRF Candidates and Their Applications.
Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, David J. Wu.
In proc. TCC (2), pp. 699-729, 2018.

BiB
TeX
Complexity Classification of Conjugated Clifford Circuits.
Adam Bouland, Joseph F. Fitzsimons, Dax Enshan Koh.
In proc. CCC, pp. 21:1-21:25, 2018.

BiB
TeX
Trading Inverses for an Irrep in the Solovay-Kitaev Theorem.
Adam Bouland, Maris Ozols.
In proc. TQC, pp. 6:1-6:15, 2018.

BiB
TeX
Bulletproofs: Short Proofs for Confidential Transactions and More.
Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, Gregory Maxwell.
In proc. IEEE Symposium on Security and Privacy, pp. 315-334, 2018.

BiB
TeX
Accelerated Methods for NonConvex Optimization.
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford.
In SIAM J. Optim., vol. 28, no. 2, pp. 1751-1772, 2018.

BiB
TeX
Multi-commodity Flow with In-Network Processing.
Moses Charikar, Yonatan Naamad, Jennifer Rexford, X. Kelvin Zou.
In proc. ALGOCLOUD, pp. 73-101, 2018.

BiB
TeX
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.
Moses Charikar, Ofir Geri, Michael P. Kim, William Kuszmaul.
In proc. ICALP, pp. 34:1-34:14, 2018.

BiB
TeX
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier.
Moses Charikar, Shay Solomon.
In proc. ICALP, pp. 33:1-33:14, 2018.

BiB
TeX
Improved pseudorandomness for unordered branching programs through local monotonicity.
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal.
In proc. STOC, pp. 363-375, 2018.

BiB
TeX
Hierarchical Clustering with Structural Constraints.
Vaggos Chatziafratis, Rad Niazadeh, Moses Charikar.
In proc. ICML, pp. 773-782, 2018.

BiB
TeX
Settling the Query Complexity of Non-adaptive Junta Testing.
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie.
In J. ACM, vol. 65, no. 6, pp. 40:1-40:18, 2018.

BiB
TeX
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations.
Michael B. Cohen, Jonathan A. Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford.
In proc. FOCS, pp. 898-909, 2018.

BiB
TeX
Approximating the Spectrum of a Graph.
David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant.
In proc. KDD, pp. 1263-1271, 2018.

BiB
TeX
Generalization Bounds for Uniformly Stable Algorithms.
Vitaly Feldman, Jan Vondrák.
In proc. NeurIPS, pp. 9770-9780, 2018.

BiB
TeX
99% Revenue via Enhanced Competition.
Michal Feldman, Ophir Friedler, Aviad Rubinstein.
In proc. EC, pp. 443-460, 2018.

BiB
TeX
A Spectral View of Adversarially Robust Features.
Shivam Garg, Vatsal Sharan, Brian Hu Zhang, Gregory Valiant.
In proc. NeurIPS, pp. 10159-10169, 2018.

BiB
TeX
Markets for Public Decision-Making.
Nikhil Garg, Ashish Goel, Benjamin Plaut.
In proc. WINE, pp. 445, 2018.

BiB
TeX
Relating Metric Distortion and Fairness of Social Choice Rules.
Ashish Goel, Reyna Hulett, Anilesh K. Krishnaswamy.
In proc. NetEcon@SIGMETRICS, pp. 4:1, 2018.

BiB
TeX
Implementing the Lexicographic Maxmin Bargaining Solution.
Ashish Goel, Anilesh K. Krishnaswamy.
In proc. WINE, pp. 449-450, 2018.

BiB
TeX
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression.
Neha Gupta, Aaron Sidford.
In proc. NeurIPS, pp. 5274-5283, 2018.

BiB
TeX
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria.
Mika Göös, Aviad Rubinstein.
In proc. FOCS, pp. 397-403, 2018.

BiB
TeX
Computing the Independence Polynomial: from the Tree Threshold down to the Roots.
Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák.
In proc. SODA, pp. 1557-1576, 2018.

BiB
TeX
Linear-time list recovery of high-rate expander codes.
Brett Hemenway, Mary Wootters.
In Inf. Comput., vol. 261, pp. 202-218, 2018.

BiB
TeX
Recovering Structured Probability Matrices.
Qingqing Huang, Sham M. Kakade, Weihao Kong, Gregory Valiant.
In proc. ITCS, pp. 46:1-46:14, 2018.

BiB
TeX
Multicalibration: Calibration for the (Computationally-Identifiable) Masses.
Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, Guy N. Rothblum.
In proc. ICML, pp. 1944-1953, 2018.

BiB
TeX
On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing.
Huseyin A. Inan, Peter Kairouz, Mary Wootters, Ayfer Özgür.
In proc. Allerton, pp. 188-195, 2018.

BiB
TeX
Accelerating Stochastic Gradient Descent for Least Squares Regression.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford.
In proc. COLT, pp. 545-604, 2018.

BiB
TeX
Efficient Õ(n/∊) Spectral Sketches for the Laplacian and its Pseudoinverse.
Arun Jambulapati, Aaron Sidford.
In proc. SODA, pp. 2487-2503, 2018.

BiB
TeX
Fairness Through Computationally-Bounded Awareness.
Michael P. Kim, Omer Reingold, Guy N. Rothblum.
In proc. NeurIPS, pp. 4847-4857, 2018.

BiB
TeX
Estimating Learnability in the Sublinear Data Regime.
Weihao Kong, Gregory Valiant.
In proc. NeurIPS, pp. 5460-5469, 2018.

BiB
TeX
Improved Decoding of Folded Reed-Solomon and Multiplicity Codes.
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters.
In proc. FOCS, pp. 212-223, 2018.

BiB
TeX
Efficient Convex Optimization with Membership Oracles.
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala.
In proc. COLT, pp. 1292-1294, 2018.

BiB
TeX
Improved List-Decodability of Random Linear Binary Codes.
Ray Li, Mary Wootters.
In proc. APPROX-RANDOM, pp. 50:1-50:19, 2018.

BiB
TeX
A Data Prism: Semi-verified learning in the small-alpha regime.
Michela Meister, Gregory Valiant.
In proc. COLT, pp. 1530-1546, 2018.

BiB
TeX
Incremental Deterministic Public-Key Encryption.
Ilya Mironov, Omkant Pandey, Omer Reingold, Gil Segev.
In J. Cryptol., vol. 31, no. 1, pp. 134-161, 2018.

BiB
TeX
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff.
In proc. ITCS, pp. 8:1-8:21, 2018.

BiB
TeX
Stability of the Lanczos Method for Matrix Function Approximation.
Cameron Musco, Christopher Musco, Aaron Sidford.
In proc. SODA, pp. 1605-1624, 2018.

BiB
TeX
Prophet Inequalities vs. Approximating Optimum Online.
Rad Niazadeh, Amin Saberi, Ali Shameli.
In proc. WINE, pp. 356-374, 2018.

BiB
TeX
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners.
Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, Virginia Vassilevska Williams.
In proc. SODA, pp. 1374-1392, 2018.

BiB
TeX
Fast Blind MIMO Decoding through Vertex Hopping.
Jonathan Perlstein, Thomas R. Dean, Mary Wootters, Andrea Goldsmith.
In proc. ACSSC, pp. 148-154, 2018.

BiB
TeX
Load-Balanced Fractional Repetition Codes.
Alexandra M. Porter, Shashwat Silas, Mary Wootters.
In proc. ISIT, pp. 2072-2076, 2018.

BiB
TeX
Learning Discrete Distributions from Untrusted Batches.
Mingda Qiao, Gregory Valiant.
In proc. ITCS, pp. 47:1-47:20, 2018.

BiB
TeX
Callisto: A Cryptographic Approach to Detecting Serial Perpetrators of Sexual Misconduct.
Anjana Rajan, Lucy Qin, David W. Archer, Dan Boneh, Tancrède Lepoint, Mayank Varia.
In proc. COMPASS, pp. 49:1-49:4, 2018.

BiB
TeX
On Taking Advantage of Multiple Requests in Error Correcting Codes.
Prasanna Ramakrishnan, Mary Wootters.
In proc. ISIT, pp. 1340-1344, 2018.

BiB
TeX
Efficient Batch Verification for UP.
Omer Reingold, Guy N. Rothblum, Ron D. Rothblum.
In proc. CCC, pp. 22:1-22:23, 2018.

BiB
TeX
Computing Exact Minimum Cuts Without Knowing the Graph.
Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg.
In proc. ITCS, pp. 39:1-39:16, 2018.

BiB
TeX
Hardness of approximate nearest neighbor search.
Aviad Rubinstein.
In proc. STOC, pp. 1260-1268, 2018.

BiB
TeX
Inapproximability of Nash Equilibrium.
Aviad Rubinstein.
In SIAM J. Comput., vol. 47, no. 3, pp. 917-959, 2018.

BiB
TeX
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity.
Aviad Rubinstein, S. Matthew Weinberg.
In ACM Trans. Economics and Comput., vol. 6, no. 3-4, pp. 19:1-19:25, 2018.

BiB
TeX
Average-radius list-recoverability of random linear codes.
Atri Rudra, Mary Wootters.
In proc. SODA, pp. 644-662, 2018.

BiB
TeX
Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits.
Rocco A. Servedio, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 56:1-56:20, 2018.

BiB
TeX
Prediction with a short memory.
Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant.
In proc. STOC, pp. 1074-1087, 2018.

BiB
TeX
Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow.
Aaron Sidford, Kevin Tian.
In proc. FOCS, pp. 922-933, 2018.

BiB
TeX
Near-Optimal Time and Sample Complexities for Solving Markov Decision Processes with a Generative Model.
Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, Yinyu Ye.
In proc. NeurIPS, pp. 5192-5202, 2018.

BiB
TeX
Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes.
Aaron Sidford, Mengdi Wang, Xian Wu, Yinyu Ye.
In proc. SODA, pp. 770-787, 2018.

BiB
TeX
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers.
Jacob Steinhardt, Moses Charikar, Gregory Valiant.
In proc. ITCS, pp. 45:1-45:21, 2018.

BiB
TeX
Sketching Linear Classifiers over Data Streams.
Kai Sheng Tai, Vatsal Sharan, Peter Bailis, Gregory Valiant.
In proc. SIGMOD Conference, pp. 757-772, 2018.

BiB
TeX
Ensemble Adversarial Training: Attacks and Defenses.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian J. Goodfellow, Dan Boneh, Patrick D. McDaniel.
In proc. ICLR (Poster), 2018.

BiB
TeX
Creating Crowdsourced Research Talks at Scale.
Rajan Vaish, Shirish Goyal, Amin Saberi, Sharad Goel.
In proc. WWW, pp. 1-11, 2018.

BiB
TeX
Local Density Estimation in High Dimensions.
Xian Wu, Moses Charikar, Vishnu Natchu.
In proc. ICML, pp. 5293-5301, 2018.
2017

BiB
TeX
The computational complexity of ball permutations.
Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban.
In proc. STOC, pp. 317-327, 2017.

BiB
TeX
Distributed PCP Theorems for Hardness of Approximation in P.
Amir Abboud, Aviad Rubinstein, R. Ryan Williams.
In proc. FOCS, pp. 25-36, 2017.

BiB
TeX
Information Aggregation in Overlapping Generations.
Mohammad Akbarpour, Amin Saberi, Ali Shameli.
In proc. WINE, pp. 401, 2017.

BiB
TeX
Approximation Algorithms for Computing Maximin Share Allocations.
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi.
In ACM Trans. Algorithms, vol. 13, no. 4, pp. 52:1-52:28, 2017.

BiB
TeX
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices.
Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi.
In proc. FOCS, pp. 914-925, 2017.

BiB
TeX
Nash Social Welfare, Matrix Permanent, and Stable Polynomials.
Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh.
In proc. ITCS, pp. 36:1-36:12, 2017.

BiB
TeX
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices.
Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi.
In proc. FOCS, pp. 914-925, 2017.

BiB
TeX
Nash Social Welfare, Matrix Permanent, and Stable Polynomials.
Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh.
In proc. ITCS, pp. 36:1-36:12, 2017.

BiB
TeX
A generalization of permanent inequalities and applications in counting and optimization.
Nima Anari, Shayan Oveis Gharan.
In proc. STOC, pp. 384-396, 2017.

BiB
TeX
An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem.
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi.
In Oper. Res., vol. 65, no. 4, pp. 1043-1061, 2017.

BiB
TeX
Min-Cost Bipartite Perfect Matching with Delays.
Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang, Roger Wattenhofer.
In proc. APPROX-RANDOM, pp. 1:1-1:20, 2017.

BiB
TeX
ERA: A Framework for Economic Resource Allocation for the Cloud.
Moshe Babaioff, Yishay Mansour, Noam Nisan, Gali Noti, Carlo Curino, Nar Ganapathy, Ishai Menache, Omer Reingold, Moshe Tennenholtz, Erez Timnat.
In proc. WWW (Companion Volume), pp. 635-642, 2017.

BiB
TeX
Communication complexity of approximate Nash equilibria.
Yakov Babichenko, Aviad Rubinstein.
In proc. STOC, pp. 878-889, 2017.

BiB
TeX
The limitations of optimization from samples.
Eric Balkanski, Aviad Rubinstein, Yaron Singer.
In proc. STOC, pp. 1016-1027, 2017.

BiB
TeX
Exponential Decay of Reconstruction Error From Binary Measurements of Sparse Signals.
Richard G. Baraniuk, Simon Foucart, Deanna Needell, Yaniv Plan, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 63, no. 6, pp. 3368-3385, 2017.

BiB
TeX
Repairing multiple failures for scalar MDS codes.
Burak Bartan, Mary Wootters.
In proc. Allerton, pp. 1145-1152, 2017.

BiB
TeX
The Hunting of the SNARK.
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer.
In J. Cryptol., vol. 30, no. 4, pp. 989-1066, 2017.

BiB
TeX
Lattice-Based DAPS and Generalizations: Self-enforcement in Signature Schemes.
Dan Boneh, Sam Kim, Valeria Nikolaenko.
In proc. ACNS, pp. 457-477, 2017.

BiB
TeX
Surnaming Schemes, Fast Verification, and Applications to SGX Technology.
Dan Boneh, Shay Gueron.
In proc. CT-RSA, pp. 149-164, 2017.

BiB
TeX
Lattice-Based SNARGs and Their Application to More Efficient Obfuscation.
Dan Boneh, Yuval Ishai, Amit Sahai, David J. Wu.
In proc. EUROCRYPT (3), pp. 247-277, 2017.

BiB
TeX
Private Puncturable PRFs from Standard Lattice Assumptions.
Dan Boneh, Sam Kim, Hart William Montgomery.
In proc. EUROCRYPT (1), pp. 415-445, 2017.

BiB
TeX
Using Level-1 Homomorphic Encryption to Improve Threshold DSA Signatures for Bitcoin Wallet Security.
Dan Boneh, Rosario Gennaro, Steven Goldfeder.
In proc. LATINCRYPT, pp. 352-377, 2017.

BiB
TeX
Constraining Pseudorandom Functions Privately.
Dan Boneh, Kevin Lewi, David J. Wu.
In proc. Public Key Cryptography (2), pp. 494-524, 2017.

BiB
TeX
Constrained Keys for Invertible Pseudorandom Functions.
Dan Boneh, Sam Kim, David J. Wu.
In proc. TCC (1), pp. 237-263, 2017.

BiB
TeX
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation.
Dan Boneh, Mark Zhandry.
In Algorithmica, vol. 79, no. 4, pp. 1233-1285, 2017.

BiB
TeX
On the Power of Statistical Zero Knowledge.
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan.
In proc. FOCS, pp. 708-719, 2017.

BiB
TeX
Can We Access a Database Both Locally and Privately?
Elette Boyle, Yuval Ishai, Rafael Pass, Mary Wootters.
In proc. TCC (2), pp. 662-693, 2017.

BiB
TeX
ETH Hardness for Densest-k-Subgraph with Perfect Completeness.
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein.
In proc. SODA, pp. 1326-1341, 2017.

BiB
TeX
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions.
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford.
In proc. ICML, pp. 654-663, 2017.

BiB
TeX
Subquadratic submodular function minimization.
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong.
In proc. STOC, pp. 1220-1231, 2017.

BiB
TeX
Learning from untrusted data.
Moses Charikar, Jacob Steinhardt, Gregory Valiant.
In proc. STOC, pp. 47-60, 2017.

BiB
TeX
Hashing-Based-Estimators for Kernel Density in High Dimensions.
Moses Charikar, Paris Siminelakis.
In proc. FOCS, pp. 1032-1043, 2017.

BiB
TeX
Local Guarantees in Graph Cuts and Clustering.
Moses Charikar, Neha Gupta, Roy Schwartz.
In proc. IPCO, pp. 136-147, 2017.

BiB
TeX
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics.
Moses Charikar, Vaggos Chatziafratis.
In proc. SODA, pp. 841-854, 2017.

BiB
TeX
Learning from untrusted data.
Moses Charikar, Jacob Steinhardt, Gregory Valiant.
In proc. STOC, pp. 47-60, 2017.

BiB
TeX
Stability and Recovery for Independence Systems.
Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák.
In proc. ESA, pp. 26:1-26:15, 2017.

BiB
TeX
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten.
In proc. APPROX-RANDOM, pp. 38:1-38:21, 2017.

BiB
TeX
Settling the Query Complexity of Non-Adaptive Junta Testing.
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie.
In proc. CCC, pp. 26:1-26:19, 2017.

BiB
TeX
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs.
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu.
In proc. STOC, pp. 410-419, 2017.

BiB
TeX
Quantum Operating Systems.
Henry Corrigan-Gibbs, David J. Wu, Dan Boneh.
In proc. HotOS, pp. 76-81, 2017.

BiB
TeX
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics.
Henry Corrigan-Gibbs, Dan Boneh.
In proc. NSDI, pp. 259-282, 2017.

BiB
TeX
Blind Joint MIMO Channel Estimation and Decoding.
Thomas R. Dean, Mary Wootters, Andrea Goldsmith.
In proc. GLOBECOM, pp. 1-6, 2017.

BiB
TeX
Arboral satisfaction: Recognition and LP approximation.
Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan C. Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, Daniel Ziegler.
In Inf. Process. Lett., vol. 127, pp. 1-5, 2017.

BiB
TeX
Guilt-free data reuse.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth.
In Commun. ACM, vol. 60, no. 4, pp. 86-93, 2017.

BiB
TeX
Certificate Transparency with Privacy.
Saba Eskandarian, Eran Messeri, Joseph Bonneau, Dan Boneh.
In Proc. Priv. Enhancing Technol., vol. 2017, no. 4, pp. 329-344, 2017.

BiB
TeX
Sequential Deliberation for Social Choice.
Brandon Fain, Ashish Goel, Kamesh Munagala, Sukolsak Sakshuwong.
In proc. WINE, pp. 177-190, 2017.

BiB
TeX
Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions.
Vitaly Feldman, Pravesh Kothari, Jan Vondrák.
In proc. ALT, pp. 540-559, 2017.

BiB
TeX
IRON: Functional Encryption using Intel SGX.
Ben Fisch, Dhinakaran Vinayagamurthy, Dan Boneh, Sergey Gorbunov.
In proc. CCS, pp. 765-782, 2017.

BiB
TeX
Locality via Partially Lifted Codes.
S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters.
In proc. APPROX-RANDOM, pp. 43:1-43:17, 2017.

BiB
TeX
Collaborative Optimization for Collective Decision-making in Continuous Spaces.
Nikhil Garg, Vijay Kamble, Ashish Goel, David Marn, Kamesh Munagala.
In proc. WWW, pp. 617-626, 2017.

BiB
TeX
Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties.
Ashish Goel, Anilesh Kollagunta Krishnaswamy, Kamesh Munagala.
In proc. EC, pp. 287-304, 2017.

BiB
TeX
Repairing Reed-Solomon Codes.
Venkatesan Guruswami, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 63, no. 9, pp. 5684-5698, 2017.

BiB
TeX
Local List Recovery of High-Rate Tensor Codes & Applications.
Brett Hemenway, Noga Ron-Zewi, Mary Wootters.
In proc. FOCS, pp. 204-215, 2017.

BiB
TeX
Limitations of piggybacking codes with low substriping.
Reyna Hulett, Mary Wootters.
In proc. Allerton, pp. 1131-1138, 2017.

BiB
TeX
An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan.
In J. ACM, vol. 64, no. 5, pp. 35:1-35:27, 2017.

BiB
TeX
A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares).
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, Aaron Sidford.
In proc. FSTTCS, pp. 2:1-2:10, 2017.

BiB
TeX
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Aaron Sidford.
In J. Mach. Learn. Res., vol. 18, pp. 223:1-223:42, 2017.

BiB
TeX
Single Pass Spectral Sparsification in Dynamic Streams.
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford.
In SIAM J. Comput., vol. 46, no. 1, pp. 456-477, 2017.

BiB
TeX
T/Key: Second-Factor Authentication From Secure Hash Chains.
Dmitry Kogan, Nathan Manohar, Dan Boneh.
In proc. CCS, pp. 983-999, 2017.

BiB
TeX
Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond.
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li.
In Proc. VLDB Endow., vol. 10, no. 12, pp. 2021-2024, 2017.

BiB
TeX
Inapproximability of VC Dimension and Littlestone's Dimension.
Pasin Manurangsi, Aviad Rubinstein.
In proc. COLT, pp. 1432-1460, 2017.

BiB
TeX
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space.
Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan.
In proc. FOCS, pp. 801-812, 2017.

BiB
TeX
Estimating the unseen from multiple populations.
Aditi Raghunathan, Gregory Valiant, James Zou.
In proc. ICML, pp. 2855-2863, 2017.

BiB
TeX
When Are Welfare Guarantees Robust?.
Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák.
In proc. APPROX-RANDOM, pp. 22:1-22:23, 2017.

BiB
TeX
Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder.
Aviad Rubinstein.
In proc. ICALP, pp. 77:1-77:13, 2017.

BiB
TeX
Detecting communities is Hard (And Counting Them is Even Harder).
Aviad Rubinstein.
In proc. ITCS, pp. 42:1-42:13, 2017.

BiB
TeX
Combinatorial Prophet Inequalities.
Aviad Rubinstein, Sahil Singla.
In proc. SODA, pp. 1671-1687, 2017.

BiB
TeX
Sorting from Noisier Samples.
Aviad Rubinstein, Shai Vardi.
In proc. SODA, pp. 960-972, 2017.

BiB
TeX
Settling the complexity of computing approximate two-player Nash equilibria.
Aviad Rubinstein.
In SIGecom Exch., vol. 15, no. 2, pp. 45-49, 2017.

BiB
TeX
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time.
Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 813-823, 2017.

BiB
TeX
Fooling Intersections of Low-Weight Halfspaces.
Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 824-835, 2017.

BiB
TeX
What Circuit Classes Can Be Learned with Non-Trivial Savings?.
Rocco A. Servedio, Li-Yang Tan.
In proc. ITCS, pp. 30:1-30:21, 2017.

BiB
TeX
How Gamification Affects Physical Activity: Large-scale Analysis of Walking Challenges in a Mobile Application.
Ali Shameli, Tim Althoff, Amin Saberi, Jure Leskovec.
In proc. WWW (Companion Volume), pp. 455-463, 2017.

BiB
TeX
Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use.
Vatsal Sharan, Gregory Valiant.
In proc. ICML, pp. 3095-3104, 2017.

BiB
TeX
Learning Overcomplete HMMs.
Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant.
In proc. NIPS, pp. 940-949, 2017.

BiB
TeX
When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors.
Aneesh Sharma, C. Seshadhri, Ashish Goel.
In proc. WWW, pp. 431-440, 2017.

BiB
TeX
Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature.
Maxim Sviridenko, Jan Vondrák, Justin Ward.
In Math. Oper. Res., vol. 42, no. 4, pp. 1197-1218, 2017.

BiB
TeX
Learning Populations of Parameters.
Kevin Tian, Weihao Kong, Gregory Valiant.
In proc. NIPS, pp. 5778-5787, 2017.

BiB
TeX
Mobilizing the Crowd to Create an Open Repository of Research Talks.
Rajan Vaish, Sharad Goel, Amin Saberi.
In proc. L@S, pp. 311-314, 2017.

BiB
TeX
Estimating the Unseen: Improved Estimators for Entropy and Other Properties.
Gregory Valiant, Paul Valiant.
In J. ACM, vol. 64, no. 6, pp. 37:1-37:41, 2017.

BiB
TeX
An Automatic Inequality Prover and Instance Optimal Identity Testing.
Gregory Valiant, Paul Valiant.
In SIAM J. Comput., vol. 46, no. 1, pp. 429-455, 2017.

BiB
TeX
Trust but Verify: Auditing the Secure Internet of Things.
Judson Wilson, Riad S. Wahby, Henry Corrigan-Gibbs, Dan Boneh, Philip Alexander Levis, Keith Winstein.
In proc. MobiSys, pp. 464-474, 2017.

BiB
TeX
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics.
Yuchen Zhang, Percy Liang, Moses Charikar.
In proc. COLT, pp. 1980-2022, 2017.
2016

BiB
TeX
The Space "Just Above" BQP.
Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee.
In proc. ITCS, pp. 271-280, 2016.

BiB
TeX
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes.
Nima Anari, Shayan Oveis Gharan, Alireza Rezaei.
In proc. COLT, pp. 103-115, 2016.

BiB
TeX
Euclidean movement minimization.
Nima Anari, MohammadAmin Fazli, Mohammad Ghodsi, MohammadAli Safari.
In J. Comb. Optim., vol. 32, no. 2, pp. 354-367, 2016.

BiB
TeX
On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems.
Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram, Shengyu Zhang.
In proc. MFCS, pp. 12:1-12:14, 2016.

BiB
TeX
Spectral Embedding of k-Cliques, Graph Partitioning and k-Means.
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop.
In proc. ITCS, pp. 301-310, 2016.

BiB
TeX
Can Almost Everybody be Almost Happy?
Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein.
In proc. ITCS, pp. 1-9, 2016.

BiB
TeX
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.
Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer.
In proc. SODA, pp. 414-429, 2016.

BiB
TeX
The Power of Optimization from Samples.
Eric Balkanski, Aviad Rubinstein, Yaron Singer.
In proc. NIPS, pp. 4017-4025, 2016.

BiB
TeX
Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks.
Dan Boneh, Henry Corrigan-Gibbs, Stuart E. Schechter.
In proc. ASIACRYPT (1), pp. 220-248, 2016.

BiB
TeX
Building a Community of Real-World Cryptographers.
Dan Boneh, Kenny Paterson, Nigel P. Smart.
In IEEE Secur. Priv., vol. 14, no. 6, pp. 7-9, 2016.

BiB
TeX
Complexity Classification of Two-Qubit Commuting Hamiltonians.
Adam Bouland, Laura Mancinska, Xue Zhang.
In proc. CCC, pp. 28:1-28:33, 2016.

BiB
TeX
Establishing quantum advantage.
Adam Bouland.
In XRDS, vol. 23, no. 1, pp. 40-44, 2016.

BiB
TeX
On the Approximability of Sparse PCA.
Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein.
In proc. COLT, pp. 623-646, 2016.

BiB
TeX
On Approximating Target Set Selection.
Moses Charikar, Yonatan Naamad, Anthony Wirth.
In proc. APPROX-RANDOM, pp. 4:1-4:16, 2016.

BiB
TeX
Near-optimal small-depth lower bounds for small distance connectivity.
Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 612-625, 2016.

BiB
TeX
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More.
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu.
In proc. FOCS, pp. 583-592, 2016.

BiB
TeX
Geometric median in nearly linear time.
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, Aaron Sidford.
In proc. STOC, pp. 9-21, 2016.

BiB
TeX
Stochastic Streams: Sample Complexity vs. Space Complexity.
Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff.
In proc. ESA, pp. 32:1-32:15, 2016.

BiB
TeX
Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations.
Shahar Dobzinski, Jan Vondrák.
In J. ACM, vol. 63, no. 1, pp. 5:1-5:19, 2016.

BiB
TeX
Equality and Social Mobility in Twitter Discussion Groups.
Katherine Ellis, Moisés Goldszmidt, Gert R. G. Lanckriet, Nina Mishra, Omer Reingold.
In proc. WSDM, pp. 523-532, 2016.

BiB
TeX
Routing under balance.
Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford.
In proc. STOC, pp. 598-611, 2016.

BiB
TeX
The Core of the Participatory Budgeting Problem.
Brandon Fain, Ashish Goel, Kamesh Munagala.
In proc. WINE, pp. 384-399, 2016.

BiB
TeX
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
Vitaly Feldman, Jan Vondrák.
In SIAM J. Comput., vol. 45, no. 3, pp. 1129-1170, 2016.

BiB
TeX
A Simple and Efficient Algorithm for Computing Market Equilibria.
Lisa Fleischer, Rahul Garg, Sanjiv Kapoor, Rohit Khandekar, Amin Saberi.
In ACM Trans. Algorithms, vol. 12, no. 3, pp. 34:1-34:15, 2016.

BiB
TeX
Principal Component Projection Without Principal Component Analysis.
Roy Frostig, Cameron Musco, Christopher Musco, Aaron Sidford.
In proc. ICML, pp. 2349-2357, 2016.

BiB
TeX
Faster Eigenvector Computation via Shift-and-Invert Preconditioning.
Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford.
In proc. ICML, pp. 2626-2634, 2016.

BiB
TeX
Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis.
Rong Ge, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford.
In proc. ICML, pp. 2741-2750, 2016.

BiB
TeX
Internet Economics [Guest editors' introduction].
Arpita Ghosh, Ashish Goel.
In IEEE Internet Comput., vol. 20, no. 1, pp. 8-10, 2016.

BiB
TeX
Network Formation of Coalition Loyalty Programs.
Arpit Goel, Vijay Kamble, Siddhartha Banerjee, Ashish Goel.
In SIGMETRICS Perform. Evaluation Rev., vol. 44, no. 3, pp. 15-20, 2016.

BiB
TeX
Towards Large-Scale Deliberative Decision-Making: Small Groups and the Importance of Triads.
Ashish Goel, David Timothy Lee.
In proc. EC, pp. 287-303, 2016.

BiB
TeX
Repairing Reed-solomon codes.
Venkatesan Guruswami, Mary Wootters.
In proc. STOC, pp. 216-226, 2016.

BiB
TeX
Strategic Classification.
Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, Mary Wootters.
In proc. ITCS, pp. 111-122, 2016.

BiB
TeX
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm.
Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, Aaron Sidford.
In proc. COLT, pp. 1147-1164, 2016.

BiB
TeX
Online Energy Storage Management: an Algorithmic Approach.
Anthony Kim, Vahid Liaghat, Junjie Qin, Amin Saberi.
In proc. APPROX-RANDOM, pp. 12:1-12:23, 2016.

BiB
TeX
CESEL: Securing a Mote for 20 Years.
Kevin Kiningham, Mark Horowitz, Philip Alexander Levis, Dan Boneh.
In proc. EWSN, pp. 307-312, 2016.

BiB
TeX
Probabilistic Matrix Inspection and Group Scheduling.
Hooyeon Lee, Ashish Goel.
In proc. IJCAI, pp. 322-328, 2016.

BiB
TeX
Stickler: Defending against Malicious Content Distribution Networks in an Unmodified Browser.
Amit Levy, Henry Corrigan-Gibbs, Dan Boneh.
In IEEE Secur. Priv., vol. 14, no. 2, pp. 22-28, 2016.

BiB
TeX
5Gen: A Framework for Prototyping Applications Using Multilinear Maps and Matrix Branching Programs.
Kevin Lewi, Alex J. Malozemoff, Daniel Apon, Brent Carmer, Adam Foltzer, Daniel Wagner, David W. Archer, Dan Boneh, Jonathan Katz, Mariana Raykova.
In proc. CCS, pp. 981-992, 2016.

BiB
TeX
Personalized PageRank Estimation and Search: A Bidirectional Approach.
Peter Lofgren, Siddhartha Banerjee, Ashish Goel.
In proc. WSDM, pp. 163-172, 2016.

BiB
TeX
Special Issue: APPROX-RANDOM 2015: Guest Editors' Foreword.
Nicole Megow, Mary Wootters.
In Theory Comput., vol. 12, no. 1, pp. 1-3, 2016.

BiB
TeX
The Complexity of Fairness Through Equilibrium.
Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein.
In ACM Trans. Economics and Comput., vol. 4, no. 4, pp. 20:1-20:19, 2016.

BiB
TeX
On the Complexity of Dynamic Mechanism Design.
Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein.
In proc. SODA, pp. 1458-1475, 2016.

BiB
TeX
Poly-logarithmic Frege depth lower bounds via an expander switching lemma.
Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 644-657, 2016.

BiB
TeX
Adaptive Condorcet-Based Stopping Rules Can Be Efficient.
Omer Reingold, Nina Narodytska.
In proc. ECAI, pp. 1704-1705, 2016.

BiB
TeX
Constant-round interactive proofs for delegating computation.
Omer Reingold, Guy N. Rothblum, Ron D. Rothblum.
In proc. STOC, pp. 49-62, 2016.

BiB
TeX
New techniques and tighter bounds for local computation algorithms.
Omer Reingold, Shai Vardi.
In J. Comput. Syst. Sci., vol. 82, no. 7, pp. 1180-1200, 2016.

BiB
TeX
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria.
Aviad Rubinstein.
In proc. FOCS, pp. 258-265, 2016.

BiB
TeX
On the Computational Complexity of Optimal Simple Mechanisms.
Aviad Rubinstein.
In proc. ITCS, pp. 21-28, 2016.

BiB
TeX
Beyond matroids: secretary problem and prophet inequality with general constraints.
Aviad Rubinstein.
In proc. STOC, pp. 324-332, 2016.

BiB
TeX
Incentive Compatibility of Bitcoin Mining Pool Reward Functions.
Okke Schrijvers, Joseph Bonneau, Dan Boneh, Tim Roughgarden.
In proc. Financial Cryptography, pp. 477-498, 2016.

BiB
TeX
Memory, Communication, and Statistical Queries.
Jacob Steinhardt, Gregory Valiant, Stefan Wager.
In proc. COLT, pp. 1490-1516, 2016.

BiB
TeX
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction.
Jacob Steinhardt, Gregory Valiant, Moses Charikar.
In proc. NIPS, pp. 4439-4447, 2016.

BiB
TeX
Instance optimal learning of discrete distributions.
Gregory Valiant, Paul Valiant.
In proc. STOC, pp. 142-155, 2016.

BiB
TeX
Privacy, Discovery, and Authentication for the Internet of Things.
David J. Wu, Ankur Taly, Asim Shankar, Dan Boneh.
In proc. ESORICS (2), pp. 301-319, 2016.

BiB
TeX
Approximate Personalized PageRank on Dynamic Graphs.
Hongyang Zhang, Peter Lofgren, Ashish Goel.
In proc. KDD, pp. 1315-1324, 2016.
2015

BiB
TeX
Computing on Authenticated Data.
Jae Hyun Ahn, Dan Boneh, Jan Camenisch, Susan Hohenberger, Abhi Shelat, Brent Waters.
In J. Cryptol., vol. 28, no. 2, pp. 351-395, 2015.

BiB
TeX
Approximation Algorithms for Computing Maximin Share Allocations.
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi.
In proc. ICALP (1), pp. 39-51, 2015.

BiB
TeX
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP.
Nima Anari, Shayan Oveis Gharan.
In proc. FOCS, pp. 20-39, 2015.

BiB
TeX
Label optimal regret bounds for online local learning.
Pranjal Awasthi, Moses Charikar, Kevin A. Lai, Andrej Risteski.
In proc. COLT, pp. 150-166, 2015.

BiB
TeX
The Hardness of Approximation of Euclidean k-Means.
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop.
In proc. SoCG, pp. 754-767, 2015.

BiB
TeX
Relax, No Need to Round: Integrality of Clustering Formulations.
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel A. Ward.
In proc. ITCS, pp. 191-200, 2015.

BiB
TeX
Testing Closeness With Unequal Sized Samples.
Bhaswar B. Bhattacharya, Gregory Valiant.
In proc. NIPS, pp. 2611-2619, 2015.

BiB
TeX
Learning Circuits with few Negations.
Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 512-527, 2015.

BiB
TeX
Approximating Boolean Functions with Depth-2 Circuits.
Eric Blais, Li-Yang Tan.
In SIAM J. Comput., vol. 44, no. 6, pp. 1583-1600, 2015.

BiB
TeX
Hosting Services on an Untrusted Cloud.
Dan Boneh, Divya Gupta, Ilya Mironov, Amit Sahai.
In proc. EUROCRYPT (2), pp. 404-436, 2015.

BiB
TeX
Semantically Secure Order-Revealing Encryption: Multi-input Functional Encryption Without Obfuscation.
Dan Boneh, Kevin Lewi, Mariana Raykova, Amit Sahai, Mark Zhandry, Joe Zimmerman.
In proc. EUROCRYPT (2), pp. 563-594, 2015.

BiB
TeX
Bypassing Worst Case Analysis: Tensor Decomposition and Clustering (Invited Talk).
Moses Samson Charikar.
In proc. FSTTCS, pp. 1, 2015.

BiB
TeX
On Multiplicative Weight Updates for Concave and Submodular Function Maximization.
Chandra Chekuri, T. S. Jayram, Jan Vondrák.
In proc. ITCS, pp. 201-210, 2015.

BiB
TeX
Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization.
Wei Chen, Fu Li, Tian Lin, Aviad Rubinstein.
In proc. EC, pp. 779-796, 2015.

BiB
TeX
Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries.
Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 519-528, 2015.

BiB
TeX
Uniform Sampling for Matrix Approximation.
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford.
In proc. ITCS, pp. 181-190, 2015.

BiB
TeX
Riposte: An Anonymous Messaging System Handling Millions of Users.
Henry Corrigan-Gibbs, Dan Boneh, David Mazières.
In proc. IEEE Symposium on Security and Privacy, pp. 321-338, 2015.

BiB
TeX
Approximate resilience, monotonicity, and the complexity of agnostic learning.
Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, Karl Wimmer.
In proc. SODA, pp. 498-511, 2015.

BiB
TeX
Provisions: Privacy-preserving Proofs of Solvency for Bitcoin Exchanges.
Gaby G. Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark, Dan Boneh.
In proc. CCS, pp. 720-731, 2015.

BiB
TeX
Strategic Formation of Credit Networks.
Pranav Dandekar, Ashish Goel, Michael P. Wellman, Bryce Wiedenbeck.
In ACM Trans. Internet Techn., vol. 15, no. 1, pp. 3:1-3:41, 2015.

BiB
TeX
Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing.
Erik D. Demaine, Tim Kaler, Quanquan C. Liu, Aaron Sidford, Adam Yedidia.
In proc. WADS, pp. 263-275, 2015.

BiB
TeX
Noise Stable Halfspaces are Close to Very Small Juntas.
Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan.
In Chic. J. Theor. Comput. Sci., vol. 2015, 2015.

BiB
TeX
Algorithmic Signaling of Features in Auction Design.
Shaddin Dughmi, Nicole Immorlica, Ryan O'Donnell, Li-Yang Tan.
In proc. SAGT, pp. 150-162, 2015.

BiB
TeX
Limitations of randomized mechanisms for combinatorial auctions.
Shaddin Dughmi, Jan Vondrák.
In Games Econ. Behav., vol. 92, pp. 370-400, 2015.

BiB
TeX
Pure Differential Privacy for Rectangle Queries via Private Partitions.
Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum.
In proc. ASIACRYPT (2), pp. 735-751, 2015.

BiB
TeX
Generalization in Adaptive Data Analysis and Holdout Reuse.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth.
In proc. NIPS, pp. 2350-2358, 2015.

BiB
TeX
Preserving Statistical Validity in Adaptive Data Analysis.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth.
In proc. STOC, pp. 117-126, 2015.

BiB
TeX
Team Formation Dynamics: A Study Using Online Learning Data.
Milad Eftekhar, Farnaz Ronaghi, Amin Saberi.
In proc. COSN, pp. 257-267, 2015.

BiB
TeX
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions.
Vitaly Feldman, Jan Vondrák.
In proc. FOCS, pp. 923-942, 2015.

BiB
TeX
Competing with the Empirical Risk Minimizer in a Single Pass.
Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford.
In proc. COLT, pp. 728-763, 2015.

BiB
TeX
Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization.
Roy Frostig, Rong Ge, Sham M. Kakade, Aaron Sidford.
In proc. ICML, pp. 2540-2548, 2015.

BiB
TeX
Connectivity in Random Forests and Credit Networks.
Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang.
In proc. SODA, pp. 2037-2048, 2015.

BiB
TeX
A Note on Modeling Retweet Cascades on Twitter.
Ashish Goel, Kamesh Munagala, Aneesh Sharma, Hongyang Zhang.
In proc. WAW, pp. 119-131, 2015.

BiB
TeX
The Who-To-Follow System at Twitter: Strategy, Algorithms, and Revenue Impact.
Ashish Goel, Pankaj Gupta, John Sirois, Dong Wang, Aneesh Sharma, Siva Gurumurthy.
In Interfaces, vol. 45, no. 1, pp. 98-107, 2015.

BiB
TeX
Finding Collisions in Interactive Protocols - Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments.
Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev.
In SIAM J. Comput., vol. 44, no. 1, pp. 193-242, 2015.

BiB
TeX
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles.
Nicholas J. A. Harvey, Jan Vondrák.
In proc. FOCS, pp. 1327-1346, 2015.

BiB
TeX
Linear-Time List Recovery of High-Rate Expander Codes.
Brett Hemenway, Mary Wootters.
In proc. ICALP (1), pp. 701-712, 2015.

BiB
TeX
Local correctability of expander codes.
Brett Hemenway, Rafail Ostrovsky, Mary Wootters.
In Inf. Comput., vol. 243, pp. 178-190, 2015.

BiB
TeX
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming.
Yin Tat Lee, Aaron Sidford.
In proc. FOCS, pp. 230-249, 2015.

BiB
TeX
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.
Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong.
In proc. FOCS, pp. 1049-1065, 2015.

BiB
TeX
Bidirectional PageRank Estimation: From Average-Case to Worst-Case.
Peter Lofgren, Siddhartha Banerjee, Ashish Goel.
In proc. WAW, pp. 164-176, 2015.

BiB
TeX
Robust Probabilistic Inference.
Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz.
In proc. SODA, pp. 449-460, 2015.

BiB
TeX
CCFI: Cryptographically Enforced Control Flow Integrity.
Ali José Mashtizadeh, Andrea Bittau, Dan Boneh, David Mazières.
In proc. CCS, pp. 941-951, 2015.

BiB
TeX
PowerSpy: Location Tracking Using Mobile Device Power Analysis.
Yan Michalevsky, Aaron Schulman, Gunaa Arumugam Veerapandian, Dan Boneh, Gabi Nakibly.
In proc. USENIX Security Symposium, pp. 785-800, 2015.

BiB
TeX
Sperner's Colorings, Hypergraph Labeling Problems and Fair Division.
Maryam Mirzakhani, Jan Vondrák.
In proc. SODA, pp. 873-886, 2015.

BiB
TeX
Lazier Than Lazy Greedy.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, Andreas Krause.
In proc. AAAI, pp. 1812-1818, 2015.

BiB
TeX
An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 1030-1048, 2015.

BiB
TeX
Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits.
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan.
In SIGACT News, vol. 46, no. 4, pp. 50-68, 2015.

BiB
TeX
Approximability of Adaptive Seeding under Knapsack Constraints.
Aviad Rubinstein, Lior Seeman, Yaron Singer.
In proc. EC, pp. 797-814, 2015.

BiB
TeX
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity.
Aviad Rubinstein, S. Matthew Weinberg.
In proc. EC, pp. 377-394, 2015.

BiB
TeX
Inapproximability of Nash Equilibrium.
Aviad Rubinstein.
In proc. STOC, pp. 409-418, 2015.

BiB
TeX
The complexity of simplicity in mechanism design.
Aviad Rubinstein.
In SIGecom Exch., vol. 14, no. 2, pp. 41-43, 2015.

BiB
TeX
It'll Probably Work Out: Improved List-Decoding Through Random Operations.
Atri Rudra, Mary Wootters.
In proc. ITCS, pp. 287-296, 2015.

BiB
TeX
Adaptivity Helps for Testing Juntas.
Rocco A. Servedio, Li-Yang Tan, John Wright.
In proc. CCC, pp. 264-279, 2015.

BiB
TeX
Information-theoretic lower bounds for convex optimization with erroneous oracles.
Yaron Singer, Jan Vondrák.
In proc. NIPS, pp. 3204-3212, 2015.

BiB
TeX
Optimal approximation for submodular and supermodular optimization with bounded curvature.
Maxim Sviridenko, Jan Vondrák, Justin Ward.
In proc. SODA, pp. 1134-1148, 2015.

BiB
TeX
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem.
Gregory Valiant.
In J. ACM, vol. 62, no. 2, pp. 13:1-13:45, 2015.
2014

BiB
TeX
On Simplex Pivoting Rules and Complexity Theory.
Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein.
In proc. IPCO, pp. 13-24, 2014.

BiB
TeX
Least Squares Revisited: Scalable Approaches for Multi-class Prediction.
Alekh Agarwal, Sham M. Kakade, Nikos Karampatziakis, Le Song, Gregory Valiant.
In proc. ICML, pp. 541-549, 2014.

BiB
TeX
Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets.
Nima Anari, Gagan Goel, Afshin Nikzad.
In proc. FOCS, pp. 266-275, 2014.

BiB
TeX
Learning Polynomials with Neural Networks.
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang.
In proc. ICML, pp. 1908-1916, 2014.

BiB
TeX
Learning Sparse Polynomial Functions.
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang.
In proc. SODA, pp. 500-510, 2014.

BiB
TeX
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright.
In ACM Trans. Comput. Theory, vol. 6, no. 1, pp. 2:1-2:20, 2014.

BiB
TeX
Fast algorithms for maximizing submodular functions.
Ashwinkumar Badanidiyuru, Jan Vondrák.
In proc. SODA, pp. 1497-1514, 2014.

BiB
TeX
Efficient Primal-Dual Graph Algorithms for MapReduce.
Bahman Bahmani, Ashish Goel, Kamesh Munagala.
In proc. WAW, pp. 59-78, 2014.

BiB
TeX
Multireference alignment using semidefinite programming.
Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu.
In proc. ITCS, pp. 459-470, 2014.

BiB
TeX
Re-incentivizing discovery: mechanisms for partial-progress sharing in research.
Siddhartha Banerjee, Ashish Goel, Anilesh Kollagunta Krishnaswamy.
In proc. EC, pp. 149-166, 2014.

BiB
TeX
Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach.
Nikhil Bansal, Moses Charikar, Ravishankar Krishnaswamy, Shi Li.
In proc. SODA, pp. 55-71, 2014.

BiB
TeX
Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold?
Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan.
In proc. COLT, pp. 1280-1282, 2014.

BiB
TeX
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability.
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan.
In proc. COLT, pp. 742-778, 2014.

BiB
TeX
Smoothed analysis of tensor decompositions.
Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan.
In proc. STOC, pp. 594-603, 2014.

BiB
TeX
Hacking Blind.
Andrea Bittau, Adam Belay, Ali José Mashtizadeh, David Mazières, Dan Boneh.
In proc. IEEE Symposium on Security and Privacy, pp. 227-242, 2014.

BiB
TeX
On DNF Approximators for Monotone Boolean Functions.
Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan.
In proc. ICALP (1), pp. 235-246, 2014.

BiB
TeX
Neuroscience meets cryptography: crypto primitives secure against rubber hose attacks.
Hristo Bojinov, Daniel Sánchez, Paul J. Reber, Dan Boneh, Patrick Lincoln.
In Commun. ACM, vol. 57, no. 5, pp. 110-118, 2014.

BiB
TeX
Bivariate Polynomials Modulo Composites and Their Applications.
Dan Boneh, Henry Corrigan-Gibbs.
In proc. ASIACRYPT (1), pp. 42-62, 2014.

BiB
TeX
Low Overhead Broadcast Encryption from Multilinear Maps.
Dan Boneh, Brent Waters, Mark Zhandry.
In proc. CRYPTO (1), pp. 206-223, 2014.

BiB
TeX
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation.
Dan Boneh, Mark Zhandry.
In proc. CRYPTO (1), pp. 480-499, 2014.

BiB
TeX
Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE and Compact Garbled Circuits.
Dan Boneh, Craig Gentry, Sergey Gorbunov, Shai Halevi, Valeria Nikolaenko, Gil Segev, Vinod Vaikuntanathan, Dhinakaran Vinayagamurthy.
In proc. EUROCRYPT, pp. 533-556, 2014.

BiB
TeX
Optimal Algorithms for Testing Closeness of Discrete Distributions.
Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant.
In proc. SODA, pp. 1193-1203, 2014.

BiB
TeX
Online Bipartite Matching with Decomposable Weights.
Moses Charikar, Monika Henzinger, Huy L. Nguyen.
In proc. ESA, pp. 260-271, 2014.

BiB
TeX
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes.
Chandra Chekuri, Jan Vondrák, Rico Zenklusen.
In SIAM J. Comput., vol. 43, no. 6, pp. 1831-1879, 2014.

BiB
TeX
New Algorithms and Lower Bounds for Monotonicity Testing.
Xi Chen, Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 286-295, 2014.

BiB
TeX
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions.
Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan.
In SIAM J. Comput., vol. 43, no. 1, pp. 231-253, 2014.

BiB
TeX
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions.
Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan.
In Theory Comput., vol. 10, pp. 27-53, 2014.

BiB
TeX
Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture.
Alina Ene, Jan Vondrák.
In proc. APPROX-RANDOM, pp. 144-159, 2014.

BiB
TeX
Optimal bounds on approximation of submodular and XOS functions by juntas.
Vitaly Feldman, Jan Vondrák.
In proc. ITA, pp. 1-10, 2014.

BiB
TeX
Disjoint Set Union with Randomized Linking.
Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan.
In proc. SODA, pp. 1005-1017, 2014.

BiB
TeX
Price-based protocols for fair resource allocation: Convergence time analysis and extension to leontief utilities.
Ashish Goel, Hamid Nazerzadeh.
In ACM Trans. Algorithms, vol. 10, no. 2, pp. 5:1-5:14, 2014.

BiB
TeX
Generalized M-2M Mapping Scheme for SLM and PTS Based OFDM Systems Without Side-Information.
Ashish Goel, Prerana Gupta, Monika Agrawal.
In Wirel. Pers. Commun., vol. 74, no. 2, pp. 285-305, 2014.

BiB
TeX
Fault tolerance in large games.
Ronen Gradwohl, Omer Reingold.
In Games Econ. Behav., vol. 86, pp. 438-457, 2014.

BiB
TeX
A New Interactive Hashing Theorem.
Iftach Haitner, Omer Reingold.
In J. Cryptol., vol. 27, no. 1, pp. 109-138, 2014.

BiB
TeX
Fast matrix completion without the condition number.
Moritz Hardt, Mary Wootters.
In proc. COLT, pp. 638-678, 2014.

BiB
TeX
Tick Tock: Building Browser Red Pills from Timing Side Channels.
Grant Ho, Dan Boneh, Lucas Ballard, Niels Provos.
In proc. WOOT, 2014.

BiB
TeX
An Experimental Study of TLS Forward Secrecy Deployments.
Lin-Shung Huang, Shrikant Adhikarla, Dan Boneh, Collin Jackson.
In IEEE Internet Comput., vol. 18, no. 6, pp. 43-51, 2014.

BiB
TeX
Exchangeability and Realizability: De Finetti Theorems on Graphs.
T. S. Jayram, Jan Vondrák.
In proc. APPROX-RANDOM, pp. 762-778, 2014.

BiB
TeX
Single Pass Spectral Sparsification in Dynamic Streams.
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford.
In proc. FOCS, pp. 561-570, 2014.

BiB
TeX
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph.
Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou.
In proc. SODA, pp. 1644-1658, 2014.

BiB
TeX
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations.
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford.
In proc. SODA, pp. 217-226, 2014.

BiB
TeX
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow.
Yin Tat Lee, Aaron Sidford.
In proc. FOCS, pp. 424-433, 2014.

BiB
TeX
Crowdsourcing for Participatory Democracies: Efficient Elicitation of Social Choice Functions.
David Timothy Lee, Ashish Goel, Tanja Aitamurto, Hélène Landemore.
In proc. HCOMP, pp. 133-142, 2014.

BiB
TeX
Satisfiability and Evolution.
Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan.
In proc. FOCS, pp. 524-530, 2014.

BiB
TeX
FAST-PPR: scaling personalized pagerank estimation for large graphs.
Peter Lofgren, Siddhartha Banerjee, Ashish Goel, Seshadhri Comandur.
In proc. KDD, pp. 1436-1445, 2014.

BiB
TeX
Deterministic Coupon Collection and Better Strong Dispersers.
Raghu Meka, Omer Reingold, Yuan Zhou.
In proc. APPROX-RANDOM, pp. 872-884, 2014.

BiB
TeX
Fast Pseudorandomness for Independence and Load Balancing - (Extended Abstract).
Raghu Meka, Omer Reingold, Guy N. Rothblum, Ron D. Rothblum.
In proc. ICALP (1), pp. 859-870, 2014.

BiB
TeX
Gyrophone: Recognizing Speech from Gyroscope Signals.
Yan Michalevsky, Dan Boneh, Gabi Nakibly.
In proc. USENIX Security Symposium, pp. 1053-1067, 2014.

BiB
TeX
New constructions of RIP matrices with fast multiplication and fewer rows.
Jelani Nelson, Eric Price, Mary Wootters.
In proc. SODA, pp. 1515-1528, 2014.

BiB
TeX
A Composition Theorem for Parity Kill Number.
Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan.
In proc. CCC, pp. 144-154, 2014.

BiB
TeX
The complexity of fairness through equilibrium.
Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein.
In proc. EC, pp. 209-226, 2014.

BiB
TeX
Pseudorandom Graphs in Data Structures.
Omer Reingold, Ron D. Rothblum, Udi Wieder.
In proc. ICALP (1), pp. 943-954, 2014.

BiB
TeX
Every list-decodable code for high noise has abundant near-optimal rate puncturings.
Atri Rudra, Mary Wootters.
In proc. STOC, pp. 764-773, 2014.

BiB
TeX
Panel: online learning platforms and data science.
Mehran Sahami, Jace Kohlmeier, Peter Norvig, Andreas Paepcke, Amin Saberi.
In proc. L@S, pp. 137-138, 2014.

BiB
TeX
Is Submodularity Testable?
C. Seshadhri, Jan Vondrák.
In Algorithmica, vol. 69, no. 1, pp. 1-25, 2014.

BiB
TeX
Multiway cut, pairwise realizable distributions, and descending thresholds.
Ankit Sharma, Jan Vondrák.
In proc. STOC, pp. 724-733, 2014.

BiB
TeX
Password Managers: Attacks and Defenses.
David Silver, Suman Jana, Dan Boneh, Eric Yawei Chen, Collin Jackson.
In proc. USENIX Security Symposium, pp. 449-464, 2014.

BiB
TeX
An Automatic Inequality Prover and Instance Optimal Identity Testing.
Gregory Valiant, Paul Valiant.
In proc. FOCS, pp. 51-60, 2014.
2013

BiB
TeX
Message-Locked Encryption for Lock-Dependent Messages.
Martín Abadi, Dan Boneh, Ilya Mironov, Ananth Raghunathan, Gil Segev.
In proc. CRYPTO (1), pp. 374-391, 2013.

BiB
TeX
Equilibrium pricing with positive externalities.
Nima AhmadiPourAnari, Shayan Ehsani, Mohammad Ghodsi, Nima Haghpanah, Nicole Immorlica, Hamid Mahini, Vahab S. Mirrokni.
In Theor. Comput. Sci., vol. 476, pp. 1-15, 2013.

BiB
TeX
Message-Passing Algorithms for Sparse Network Alignment.
Mohsen Bayati, David F. Gleich, Amin Saberi, Ying Wang.
In ACM Trans. Knowl. Discov. Data, vol. 7, no. 1, pp. 3:1-3:31, 2013.

BiB
TeX
Approximating Boolean Functions with Depth-2 Circuits.
Eric Blais, Li-Yang Tan.
In proc. CCC, pp. 74-85, 2013.

BiB
TeX
Hypercontractivity Via the Entropy Method.
Eric Blais, Li-Yang Tan.
In Theory Comput., vol. 9, pp. 889-896, 2013.

BiB
TeX
Private Database Queries Using Somewhat Homomorphic Encryption.
Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, David J. Wu.
In proc. ACNS, pp. 102-118, 2013.

BiB
TeX
Function-Private Subspace-Membership Encryption and Its Applications.
Dan Boneh, Ananth Raghunathan, Gil Segev.
In proc. ASIACRYPT (1), pp. 255-275, 2013.

BiB
TeX
Constrained Pseudorandom Functions and Their Applications.
Dan Boneh, Brent Waters.
In proc. ASIACRYPT (2), pp. 280-300, 2013.

BiB
TeX
Key Homomorphic PRFs and Their Applications.
Dan Boneh, Kevin Lewi, Hart William Montgomery, Ananth Raghunathan.
In proc. CRYPTO (1), pp. 410-428, 2013.

BiB
TeX
Function-Private Identity-Based Encryption: Hiding the Function in Functional Encryption.
Dan Boneh, Ananth Raghunathan, Gil Segev.
In proc. CRYPTO (2), pp. 461-478, 2013.

BiB
TeX
Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World.
Dan Boneh, Mark Zhandry.
In proc. CRYPTO (2), pp. 361-379, 2013.

BiB
TeX
Quantum-Secure Message Authentication Codes.
Dan Boneh, Mark Zhandry.
In proc. EUROCRYPT, pp. 592-608, 2013.

BiB
TeX
Balls and Bins: Smaller Hash Families and Faster Evaluation.
L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder.
In SIAM J. Comput., vol. 42, no. 3, pp. 1030-1050, 2013.

BiB
TeX
Ensuring high-quality randomness in cryptographic key generation.
Henry Corrigan-Gibbs, Wendy Mu, Dan Boneh, Bryan Ford.
In proc. CCS, pp. 685-696, 2013.

BiB
TeX
Biased assimilation, homophily, and the dynamics of polarization.
Pranav Dandekar, Ashish Goel, David T. Lee.
In Proc. Natl. Acad. Sci. USA, vol. 110, no. 15, pp. 5791-5796, 2013.

BiB
TeX
Learning Sums of Independent Integer Random Variables.
Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 217-226, 2013.

BiB
TeX
Testing k-Modal Distributions: Optimal Algorithms via Reductions.
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant.
In proc. SODA, pp. 1833-1852, 2013.

BiB
TeX
Communication Complexity of Combinatorial Auctions with Submodular Valuations.
Shahar Dobzinski, Jan Vondrák.
In proc. SODA, pp. 1205-1215, 2013.

BiB
TeX
Accurate Decoding of Pooled Sequenced Data Using Compressed Sensing.
Denisa Duma, Mary Wootters, Anna C. Gilbert, Hung Q. Ngo, Atri Rudra, Matthew Alpert, Timothy J. Close, Gianfranco Ciardo, Stefano Lonardi.
In proc. WABI, pp. 70-84, 2013.

BiB
TeX
Eagle-eyed elephant: split-oriented indexing in Hadoop.
Mohamed Y. Eltabakh, Fatma Özcan, Yannis Sismanis, Peter J. Haas, Hamid Pirahesh, Jan Vondrák.
In proc. EDBT, pp. 89-100, 2013.

BiB
TeX
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems.
Alina Ene, Jan Vondrák, Yi Wu.
In proc. SODA, pp. 306-325, 2013.

BiB
TeX
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees.
Vitaly Feldman, Pravesh Kothari, Jan Vondrák.
In proc. COLT, pp. 711-740, 2013.

BiB
TeX
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
Vitaly Feldman, Jan Vondrák.
In proc. FOCS, pp. 227-236, 2013.

BiB
TeX
Structure and learning of valuation functions.
Vitaly Feldman, Jan Vondrák.
In SIGecom Exch., vol. 12, no. 2, pp. 50-53, 2013.

BiB
TeX
OSS: Using Online Scanning Services for Censorship Circumvention.
David Fifield, Gabi Nakibly, Dan Boneh.
In proc. Privacy Enhancing Technologies, pp. 185-204, 2013.

BiB
TeX
On Variants of the Matroid Secretary Problem.
Shayan Oveis Gharan, Jan Vondrák.
In Algorithmica, vol. 67, no. 4, pp. 472-497, 2013.

BiB
TeX
SER analysis of PTS based techniques for PAPR reduction in OFDM systems.
Ashish Goel, Prerana Gupta, Monika Agrawal.
In Digit. Signal Process., vol. 23, no. 1, pp. 302-313, 2013.

BiB
TeX
Perfect Matchings in O(nlog n) Time in Regular Bipartite Graphs.
Ashish Goel, Michael Kapralov, Sanjeev Khanna.
In SIAM J. Comput., vol. 42, no. 3, pp. 1392-1404, 2013.

BiB
TeX
Joint ICI Cancellation and PAPR Reduction in OFDM Systems Without Side Information.
Ashish Goel, Prerana Gupta, Monika Agrawal.
In Wirel. Pers. Commun., vol. 71, no. 4, pp. 2605-2623, 2013.

BiB
TeX
DNF sparsification and a faster deterministic counting algorithm.
Parikshit Gopalan, Raghu Meka, Omer Reingold.
In Comput. Complex., vol. 22, no. 2, pp. 275-310, 2013.

BiB
TeX
Pseudorandom Generators for Combinatorial Shapes.
Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman.
In SIAM J. Comput., vol. 42, no. 3, pp. 1051-1076, 2013.

BiB
TeX
WTF: the who to follow service at Twitter.
Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, Reza Zadeh.
In proc. WWW, pp. 505-514, 2013.

BiB
TeX
Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions.
Iftach Haitner, Omer Reingold, Salil P. Vadhan.
In SIAM J. Comput., vol. 42, no. 3, pp. 1405-1430, 2013.

BiB
TeX
Local Correctability of Expander Codes.
Brett Hemenway, Rafail Ostrovsky, Mary Wootters.
In proc. ICALP (1), pp. 540-551, 2013.

BiB
TeX
Online Submodular Welfare Maximization: Greedy is Optimal.
Michael Kapralov, Ian Post, Jan Vondrák.
In proc. SODA, pp. 1216-1225, 2013.

BiB
TeX
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time.
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu.
In proc. STOC, pp. 911-920, 2013.

BiB
TeX
Multi-Tuple Deletion Propagation: Approximations and Complexity.
Benny Kimelfeld, Jan Vondrák, David P. Woodruff.
In Proc. VLDB Endow., vol. 6, no. 13, pp. 1558-1569, 2013.

BiB
TeX
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems.
Yin Tat Lee, Aaron Sidford.
In proc. FOCS, pp. 147-156, 2013.

BiB
TeX
Matroid Matching: The Power of Local Search.
Jon Lee, Maxim Sviridenko, Jan Vondrák.
In SIAM J. Comput., vol. 42, no. 1, pp. 357-379, 2013.

BiB
TeX
Dynamic Pay-Per-Action Mechanisms and Applications to Online Advertising.
Hamid Nazerzadeh, Amin Saberi, Rakesh Vohra.
In Oper. Res., vol. 61, no. 1, pp. 98-111, 2013.

BiB
TeX
Privacy-preserving matrix factorization.
Valeria Nikolaenko, Stratis Ioannidis, Udi Weinsberg, Marc Joye, Nina Taft, Dan Boneh.
In proc. CCS, pp. 801-812, 2013.

BiB
TeX
Privacy-Preserving Ridge Regression on Hundreds of Millions of Records.
Valeria Nikolaenko, Udi Weinsberg, Stratis Ioannidis, Marc Joye, Dan Boneh, Nina Taft.
In proc. IEEE Symposium on Security and Privacy, pp. 334-348, 2013.

BiB
TeX
A Composition Theorem for the Fourier Entropy-Influence Conjecture.
Ryan O'Donnell, Li-Yang Tan.
In proc. ICALP (1), pp. 780-791, 2013.

BiB
TeX
Pseudorandomness for Regular Branching Programs via Fourier Analysis.
Omer Reingold, Thomas Steinke, Salil P. Vadhan.
In proc. APPROX-RANDOM, pp. 655-670, 2013.

BiB
TeX
On the Average Sensitivity and Density of k-CNF Formulas.
Dominik Scheder, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 683-698, 2013.

BiB
TeX
Estimating the Unseen: Improved Estimators for Entropy and other Properties.
Paul Valiant, Gregory Valiant.
In proc. NIPS, pp. 2157-2165, 2013.

BiB
TeX
Symmetry and Approximability of Submodular Maximization Problems.
Jan Vondrák.
In SIAM J. Comput., vol. 42, no. 1, pp. 265-304, 2013.

BiB
TeX
Lower bounds for quantized matrix completion.
Mary Wootters, Yaniv Plan, Mark A. Davenport, Ewout van den Berg.
In proc. ISIT, pp. 296-300, 2013.

BiB
TeX
On the list decodability of random linear codes with large error rates.
Mary Wootters.
In proc. STOC, pp. 853-860, 2013.

BiB
TeX
Binary Opinion Dynamics with Stubborn Agents.
Mehmet Ercan Yildiz, Asuman E. Ozdaglar, Daron Acemoglu, Amin Saberi, Anna Scaglione.
In ACM Trans. Economics and Comput., vol. 1, no. 4, pp. 19:1-19:30, 2013.

BiB
TeX
On the precision of social and information networks.
Reza Bosagh Zadeh, Ashish Goel, Kamesh Munagala, Aneesh Sharma.
In proc. COSN, pp. 63-74, 2013.

BiB
TeX
Dimension independent similarity computation.
Reza Bosagh Zadeh, Ashish Goel.
In J. Mach. Learn. Res., vol. 14, no. 1, pp. 1605-1626, 2013.
2012

BiB
TeX
Price of Correlations in Stochastic Optimization.
Shipra Agrawal, Yichuan Ding, Amin Saberi, Yinyu Ye.
In Oper. Res., vol. 60, no. 1, pp. 150-162, 2012.

BiB
TeX
Computing on Authenticated Data.
Jae Hyun Ahn, Dan Boneh, Jan Camenisch, Susan Hohenberger, Abhi Shelat, Brent Waters.
In proc. TCC, pp. 1-20, 2012.

BiB
TeX
Santa claus meets hypergraph matchings.
Arash Asadpour, Uriel Feige, Amin Saberi.
In ACM Trans. Algorithms, vol. 8, no. 3, pp. 24:1-24:9, 2012.

BiB
TeX
Efficient distributed locality sensitive hashing.
Bahman Bahmani, Ashish Goel, Rajendra Shinde.
In proc. CIKM, pp. 2174-2178, 2012.

BiB
TeX
Partitioned multi-indexing: bringing order to social search.
Bahman Bahmani, Ashish Goel.
In proc. WWW, pp. 399-408, 2012.

BiB
TeX
On Quadratic Programming with a Ratio Objective.
Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan.
In proc. ICALP (1), pp. 109-120, 2012.

BiB
TeX
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph.
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou.
In proc. SODA, pp. 388-405, 2012.

BiB
TeX
Neuroscience Meets Cryptography: Designing Crypto Primitives Secure Against Rubber Hose Attacks.
Hristo Bojinov, Daniel Sánchez, Paul J. Reber, Dan Boneh, Patrick Lincoln.
In proc. USENIX Security Symposium, pp. 129-141, 2012.

BiB
TeX
Pairing-Based Cryptography: Past, Present, and Future.
Dan Boneh.
In proc. ASIACRYPT, pp. 1, 2012.

BiB
TeX
Targeted malleability: homomorphic encryption for restricted computations.
Dan Boneh, Gil Segev, Brent Waters.
In proc. ITCS, pp. 350-366, 2012.

BiB
TeX
Functional encryption: a new vision for public-key cryptography.
Dan Boneh, Amit Sahai, Brent Waters.
In Commun. ACM, vol. 55, no. 11, pp. 56-64, 2012.

BiB
TeX
On Tractable Parameterizations of Graph Isomorphism.
Adam Bouland, Anuj Dawar, Eryk Kopczynski.
In proc. IPEC, pp. 218-230, 2012.

BiB
TeX
HBIST: An approach towards zero external test cost.
Mayur Bubna, Kaushik Roy, Ashish Goel.
In proc. VTS, pp. 13-18, 2012.

BiB
TeX
SessionJuggler: secure web login from an untrusted terminal using session hijacking.
Elie Bursztein, Chinmay Soman, Dan Boneh, John C. Mitchell.
In proc. WWW, pp. 321-330, 2012.

BiB
TeX
A Dependent LP-Rounding Approach for the k-Median Problem.
Moses Charikar, Shi Li.
In proc. ICALP (1), pp. 194-205, 2012.

BiB
TeX
Biased Assimilation, Homophily, and the Dynamics of Polarization - (Working Paper).
Pranav Dandekar, Ashish Goel, David Lee.
In proc. WINE, pp. 559, 2012.

BiB
TeX
Strategic formation of credit networks.
Pranav Dandekar, Ashish Goel, Michael P. Wellman, Bryce Wiedenbeck.
In proc. WWW, pp. 559-568, 2012.

BiB
TeX
Algorithmic Solutions for Envy-Free Cake Cutting.
Xiaotie Deng, Qi Qi, Amin Saberi.
In Oper. Res., vol. 60, no. 6, pp. 1461-1476, 2012.

BiB
TeX
The computational complexity of truthfulness in combinatorial auctions.
Shahar Dobzinski, Jan Vondrák.
In proc. EC, pp. 405-422, 2012.

BiB
TeX
From query complexity to computational complexity.
Shahar Dobzinski, Jan Vondrák.
In proc. STOC, pp. 1107-1116, 2012.

BiB
TeX
High-confidence near-duplicate image detection.
Wei Dong, Zhe Wang, Moses Charikar, Kai Li.
In proc. ICMR, pp. 1, 2012.

BiB
TeX
Fairness through awareness.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel.
In proc. ITCS, pp. 214-226, 2012.

BiB
TeX
Evading Censorship with Browser-Based Proxies.
David Fifield, Nate Hardison, Jonathan D. Ellithorpe, Emily Stark, Dan Boneh, Roger Dingledine, Phillip A. Porras.
In proc. Privacy Enhancing Technologies, pp. 239-258, 2012.

BiB
TeX
Distributed node placement algorithms for constructing well-connected sensor networks.
Arthur J. Friend, Vahideh H. Manshadi, Amin Saberi.
In proc. INFOCOM, pp. 810-818, 2012.

BiB
TeX
The most dangerous code in the world: validating SSL certificates in non-browser software.
Martin Georgiev, Subodh Iyengar, Suman Jana, Rishita Anubhai, Dan Boneh, Vitaly Shmatikov.
In proc. CCS, pp. 38-49, 2012.

BiB
TeX
Recovering simple signals.
Anna C. Gilbert, Brett Hemenway, Atri Rudra, Martin J. Strauss, Mary Wootters.
In proc. ITA, pp. 382-391, 2012.

BiB
TeX
Reusable low-error compressive sampling schemes through privacy.
Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, Mary Wootters.
In proc. SSP, pp. 536-539, 2012.

BiB
TeX
On the communication and streaming complexity of maximum bipartite matching.
Ashish Goel, Michael Kapralov, Sanjeev Khanna.
In proc. SODA, pp. 468-485, 2012.

BiB
TeX
A Game-Theoretic Model of Attention in Social Networks.
Ashish Goel, Farnaz Ronaghi.
In proc. WAW, pp. 78-92, 2012.

BiB
TeX
Triadic Consensus - A Randomized Algorithm for Voting in a Crowd.
Ashish Goel, David Lee.
In proc. WINE, pp. 434-447, 2012.

BiB
TeX
Optimized data allocation & combining scheme for ICI self cancellation in OFDM systems.
Ashish Goel, Ankit Nagpal, Jasmeet Kaur.
In proc. WOCN, pp. 1-4, 2012.

BiB
TeX
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk.
Ashish Goel, Ian Post.
In Theory Comput., vol. 8, no. 1, pp. 351-368, 2012.

BiB
TeX
DNF Sparsification and a Faster Deterministic Counting Algorithm.
Parikshit Gopalan, Raghu Meka, Omer Reingold.
In proc. CCC, pp. 126-135, 2012.

BiB
TeX
Better Pseudorandom Generators from Milder Pseudorandom Restrictions.
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan.
In proc. FOCS, pp. 120-129, 2012.

BiB
TeX
Size and Treewidth Bounds for Conjunctive Queries.
Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, Paul Valiant.
In J. ACM, vol. 59, no. 3, pp. 16:1-16:35, 2012.

BiB
TeX
Disentangling Gaussians.
Adam Tauman Kalai, Ankur Moitra, Gregory Valiant.
In Commun. ACM, vol. 55, no. 2, pp. 113-120, 2012.

BiB
TeX
Maximizing Conjunctive Views in Deletion Propagation.
Benny Kimelfeld, Jan Vondrák, Ryan Williams.
In ACM Trans. Database Syst., vol. 37, no. 4, pp. 24:1-24:37, 2012.

BiB
TeX
Privacy and Cybersecurity: The Next 100 Years.
Carl E. Landwehr, Dan Boneh, John C. Mitchell, Steven M. Bellovin, Susan Landau, Michael E. Lesk.
In Proc. IEEE, vol. 100, no. Centennial-Issue, pp. 1659-1673, 2012.

BiB
TeX
Bootstrapping Communications into an Anti-Censorship System.
Patrick Lincoln, Ian Mason, Phillip A. Porras, Vinod Yegneswaran, Zachary Weinberg, Jeroen Massar, William Allen Simpson, Paul Vixie, Dan Boneh.
In proc. FOCI, 2012.

BiB
TeX
Online Optimization with Uncertain Information.
Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi.
In ACM Trans. Algorithms, vol. 8, no. 1, pp. 2:1-2:29, 2012.

BiB
TeX
Dynamics of prisoner's dilemma and the evolution of cooperation on networks.
Vahideh H. Manshadi, Amin Saberi.
In proc. ITCS, pp. 227-235, 2012.

BiB
TeX
Online Stochastic Matching: Online Actions Based on Offline Statistics.
Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi.
In Math. Oper. Res., vol. 37, no. 4, pp. 559-573, 2012.

BiB
TeX
Converting Online Algorithms to Local Computation Algorithms.
Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie.
In proc. ICALP (1), pp. 653-664, 2012.

BiB
TeX
Incremental Deterministic Public-Key Encryption.
Ilya Mironov, Omkant Pandey, Omer Reingold, Gil Segev.
In proc. EUROCRYPT, pp. 628-644, 2012.

BiB
TeX
Persistent OSPF Attacks.
Gabi Nakibly, Alex Kirshon, Dima Gonikman, Dan Boneh.
In proc. NDSS, 2012.

BiB
TeX
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.
Rocco A. Servedio, Li-Yang Tan, Justin Thaler.
In proc. COLT, pp. 14.1-14.19, 2012.

BiB
TeX
The Case for Prefetching and Prevalidating TLS Server Certificates.
Emily Stark, Lin-Shung Huang, Dinesh Israni, Collin Jackson, Dan Boneh.
In proc. NDSS, 2012.

BiB
TeX
Who killed my battery?: analyzing mobile browser energy consumption.
Narendran Thiagarajan, Gaurav Aggarwal, Angela Nicoara, Dan Boneh, Jatinder Pal Singh.
In proc. WWW, pp. 41-50, 2012.

BiB
TeX
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas.
Gregory Valiant.
In proc. FOCS, pp. 11-20, 2012.

BiB
TeX
StegoTorus: a camouflage proxy for the Tor anonymity system.
Zachary Weinberg, Jeffrey Wang, Vinod Yegneswaran, Linda Briesemeister, Steven Cheung, Frank Wang, Dan Boneh.
In proc. CCS, pp. 109-120, 2012.
2011

BiB
TeX
Fitting Tree Metrics: Hierarchical Clustering and Phylogeny.
Nir Ailon, Moses Charikar.
In SIAM J. Comput., vol. 40, no. 5, pp. 1275-1291, 2011.

BiB
TeX
Near Linear Lower Bound for Dimension Reduction in L1.
Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen.
In proc. FOCS, pp. 315-323, 2011.

BiB
TeX
Only valuable experts can be valued.
Moshe Babaioff, Liad Blumrosen, Nicolas S. Lambert, Omer Reingold.
In proc. EC, pp. 221-222, 2011.

BiB
TeX
Improved Approximation Results for Stochastic Knapsack Problems.
Anand Bhalgat, Ashish Goel, Sanjeev Khanna.
In proc. SODA, pp. 1647-1665, 2011.

BiB
TeX
Address space randomization for mobile devices.
Hristo Bojinov, Dan Boneh, Rich Cannings, Iliyan Malchev.
In proc. WISEC, pp. 127-138, 2011.

BiB
TeX
Mobile token-based authentication on a budget.
Hristo Bojinov, Dan Boneh.
In proc. HotMobile, pp. 14-19, 2011.

BiB
TeX
Random Oracles in a Quantum World.
Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, Mark Zhandry.
In proc. ASIACRYPT, pp. 41-69, 2011.

BiB
TeX
Homomorphic Signatures for Polynomial Functions.
Dan Boneh, David Mandell Freeman.
In proc. EUROCRYPT, pp. 149-168, 2011.

BiB
TeX
Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures.
Dan Boneh, David Mandell Freeman.
In proc. Public Key Cryptography, pp. 1-16, 2011.

BiB
TeX
Functional Encryption: Definitions and Challenges.
Dan Boneh, Amit Sahai, Brent Waters.
In proc. TCC, pp. 253-273, 2011.

BiB
TeX
Recent ideas for circumventing internet filtering.
Dan Boneh.
In XRDS, vol. 18, no. 2, pp. 36-40, 2011.

BiB
TeX
Efficient Selective Identity-Based Encryption Without Random Oracles.
Dan Boneh, Xavier Boyen.
In J. Cryptol., vol. 24, no. 4, pp. 659-693, 2011.

BiB
TeX
OpenConflict: Preventing Real Time Map Hacks in Online Games.
Elie Bursztein, Mike Hamburg, Jocelyn Lagarenne, Dan Boneh.
In proc. IEEE Symposium on Security and Privacy, pp. 506-520, 2011.

BiB
TeX
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.
Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák.
In SIAM J. Comput., vol. 40, no. 6, pp. 1740-1766, 2011.

BiB
TeX
Balls and Bins: Smaller Hash Families and Faster Evaluation.
L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder.
In proc. FOCS, pp. 599-608, 2011.

BiB
TeX
Social Influence and Evolution of Market Share.
Simla Ceyhan, Mohammad Mousavi, Amin Saberi.
In Internet Math., vol. 7, no. 2, pp. 107-134, 2011.

BiB
TeX
Tight Hardness Results for Minimizing Discrepancy.
Moses Charikar, Alantha Newman, Aleksandar Nikolov.
In proc. SODA, pp. 1607-1614, 2011.

BiB
TeX
Improved Approximation Algorithms for Label Cover Problems.
Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff.
In Algorithmica, vol. 61, no. 1, pp. 190-206, 2011.

BiB
TeX
Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.
Chandra Chekuri, Jan Vondrák, Rico Zenklusen.
In proc. SODA, pp. 1080-1097, 2011.

BiB
TeX
S-T connectivity on digraphs with a known stationary distribution.
Kai-Min Chung, Omer Reingold, Salil P. Vadhan.
In ACM Trans. Algorithms, vol. 7, no. 3, pp. 30:1-30:21, 2011.

BiB
TeX
On Principles of Egocentric Person Search in Social Networks.
Sara Cohen, Benny Kimelfeld, Georgia Koutrika, Jan Vondrák.
In proc. VLDS, pp. 3-6, 2011.

BiB
TeX
Liquidity in credit networks: a little trust goes a long way.
Pranav Dandekar, Ashish Goel, Ramesh Govindan, Ian Post.
In proc. EC, pp. 147-156, 2011.

BiB
TeX
Discrete Fixed Points: Models, Complexities, and Applications.
Xiaotie Deng, Qi Qi, Amin Saberi, Jie Zhang.
In Math. Oper. Res., vol. 36, no. 4, pp. 636-652, 2011.

BiB
TeX
Efficient k-nearest neighbor graph construction for generic similarity measures.
Wei Dong, Moses Charikar, Kai Li.
In proc. WWW, pp. 577-586, 2011.

BiB
TeX
Limitations of Randomized Mechanisms for Combinatorial Auctions.
Shaddin Dughmi, Jan Vondrák.
In proc. FOCS, pp. 502-511, 2011.

BiB
TeX
Euclidean Movement Minimization.
MohammadAmin Fazli, MohammadAli Safari, Nima Anari, Pooya Jalaly Khalilabadi, Mohammad Ghodsi.
In proc. CCCG, 2011.

BiB
TeX
Maximizing Non-monotone Submodular Functions.
Uriel Feige, Vahab S. Mirrokni, Jan Vondrák.
In SIAM J. Comput., vol. 40, no. 4, pp. 1133-1153, 2011.

BiB
TeX
On Variants of the Matroid Secretary Problem.
Shayan Oveis Gharan, Jan Vondrák.
In proc. ESA, pp. 335-346, 2011.

BiB
TeX
A Randomized Rounding Approach to the Traveling Salesman Problem.
Shayan Oveis Gharan, Amin Saberi, Mohit Singh.
In proc. FOCS, pp. 550-559, 2011.

BiB
TeX
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus.
Shayan Oveis Gharan, Amin Saberi.
In proc. SODA, pp. 967-975, 2011.

BiB
TeX
Submodular Maximization by Simulated Annealing.
Shayan Oveis Gharan, Jan Vondrák.
In proc. SODA, pp. 1098-1116, 2011.

BiB
TeX
Two new phase sequence sets for PAPR reduction in SLM-OFDM systems without side information.
Ashish Goel, Prerana Gupta Poddar, Monika Agrawal.
In proc. ACWR, pp. 35-40, 2011.

BiB
TeX
Integrated Design & Test: Conquering the Conflicting Requirements of Low-Power, Variation-Tolerance and Test Cost.
Ashish Goel, Swaroop Ghosh, Mesut Meterelliyoz, Jeff Parkhurst, Kaushik Roy.
In proc. Asian Test Symposium, pp. 486-491, 2011.

BiB
TeX
A renewable, modular, and time-responsive DNA circuit.
Ashish Goel, Morteza Ibrahimi.
In Nat. Comput., vol. 10, no. 1, pp. 467-485, 2011.

BiB
TeX
Pseudorandom generators for combinatorial shapes.
Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman.
In proc. STOC, pp. 253-262, 2011.

BiB
TeX
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant.
Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar.
In SIAM J. Comput., vol. 40, no. 3, pp. 878-914, 2011.

BiB
TeX
On the Power of the Randomized Iterate.
Iftach Haitner, Danny Harnik, Omer Reingold.
In SIAM J. Comput., vol. 40, no. 6, pp. 1486-1528, 2011.

BiB
TeX
Public Key Locally Decodable Codes with Short Keys.
Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wootters.
In proc. APPROX-RANDOM, pp. 605-615, 2011.

BiB
TeX
Maximizing conjunctive views in deletion propagation.
Benny Kimelfeld, Jan Vondrák, Ryan Williams.
In proc. PODS, pp. 187-198, 2011.

BiB
TeX
A Read-Disturb-Free, Differential Sensing 1R/1W Port, 8T Bitcell Array.
Jaydeep P. Kulkarni, Ashish Goel, Patrick Ndai, Kaushik Roy.
In IEEE Trans. Very Large Scale Integr. Syst., vol. 19, no. 9, pp. 1727-1730, 2011.

BiB
TeX
Memory-based embedded digital ATE.
Dongsoo Lee, Sang Phill Park, Ashish Goel, Kaushik Roy.
In proc. VTS, pp. 266-271, 2011.

BiB
TeX
Online Stochastic Matching: Online Actions Based on Offline Statistics.
Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi.
In proc. SODA, pp. 1285-1294, 2011.

BiB
TeX
Location Privacy via Private Proximity Testing.
Arvind Narayanan, Narendran Thiagarajan, Mugdha Lakhani, Michael Hamburg, Dan Boneh.
In proc. NDSS, 2011.

BiB
TeX
Best-Response Mechanisms.
Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar.
In proc. ICS, pp. 155-165, 2011.

BiB
TeX
Incentive-compatible distributed greedy protocols.
Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar.
In proc. PODC, pp. 335-336, 2011.

BiB
TeX
Best-response auctions.
Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar.
In proc. EC, pp. 351-360, 2011.

BiB
TeX
When is it best to best-respond?
Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar.
In SIGecom Exch., vol. 10, no. 2, pp. 16-18, 2011.

BiB
TeX
Is Submodularity Testable?
C. Seshadhri, Jan Vondrák.
In proc. ICS, pp. 195-210, 2011.

BiB
TeX
The Power of Linear Estimators.
Gregory Valiant, Paul Valiant.
In proc. FOCS, pp. 403-412, 2011.

BiB
TeX
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs.
Gregory Valiant, Paul Valiant.
In proc. STOC, pp. 685-694, 2011.

BiB
TeX
Submodular function maximization via the multilinear relaxation and contention resolution schemes.
Jan Vondrák, Chandra Chekuri, Rico Zenklusen.
In proc. STOC, pp. 783-792, 2011.
2010

BiB
TeX
An Analysis of Private Browsing Modes in Modern Browsers.
Gaurav Aggarwal, Elie Bursztein, Collin Jackson, Dan Boneh.
In proc. USENIX Security Symposium, pp. 79-94, 2010.

BiB
TeX
Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE.
Shweta Agrawal, Dan Boneh, Xavier Boyen.
In proc. CRYPTO, pp. 98-115, 2010.

BiB
TeX
Efficient Lattice (H)IBE in the Standard Model.
Shweta Agrawal, Dan Boneh, Xavier Boyen.
In proc. EUROCRYPT, pp. 553-572, 2010.

BiB
TeX
Preventing Pollution Attacks in Multi-source Network Coding.
Shweta Agrawal, Dan Boneh, Xavier Boyen, David Mandell Freeman.
In proc. Public Key Cryptography, pp. 161-176, 2010.

BiB
TeX
Correlation Robust Stochastic Optimization.
Shipra Agrawal, Yichuan Ding, Amin Saberi, Yinyu Ye.
In proc. SODA, pp. 1087-1096, 2010.

BiB
TeX
Equilibrium Pricing with Positive Externalities (Extended Abstract).
Nima Anari, Shayan Ehsani, Mohammad Ghodsi, Nima Haghpanah, Nicole Immorlica, Hamid Mahini, Vahab S. Mirrokni.
In proc. WINE, pp. 424-431, 2010.

BiB
TeX
An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem.
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi.
In proc. SODA, pp. 379-389, 2010.

BiB
TeX
An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods.
Arash Asadpour, Amin Saberi.
In SIAM J. Comput., vol. 39, no. 7, pp. 2970-2989, 2010.

BiB
TeX
Approximating power indices: theoretical and empirical analysis.
Yoram Bachrach, Evangelos Markakis, Ezra Resnick, Ariel D. Procaccia, Jeffrey S. Rosenschein, Amin Saberi.
In Auton. Agents Multi Agent Syst., vol. 20, no. 2, pp. 105-122, 2010.

BiB
TeX
Fast Incremental and Personalized PageRank.
Bahman Bahmani, Abdur Chowdhury, Ashish Goel.
In Proc. VLDB Endow., vol. 4, no. 3, pp. 173-184, 2010.

BiB
TeX
A Sequential Algorithm for Generating Random Graphs.
Mohsen Bayati, Jeong Han Kim, Amin Saberi.
In Algorithmica, vol. 58, no. 4, pp. 860-910, 2010.

BiB
TeX
Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph.
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan.
In proc. STOC, pp. 201-210, 2010.

BiB
TeX
The Case for Ubiquitous Transport-Level Encryption.
Andrea Bittau, Michael Hamburg, Mark Handley, David Mazières, Dan Boneh.
In proc. USENIX Security Symposium, pp. 403-418, 2010.

BiB
TeX
Kamouflage: Loss-Resistant Password Management.
Hristo Bojinov, Elie Bursztein, Xavier Boyen, Dan Boneh.
In proc. ESORICS, pp. 286-302, 2010.

BiB
TeX
The emergence of cross channel scripting.
Hristo Bojinov, Elie Bursztein, Dan Boneh.
In Commun. ACM, vol. 53, no. 8, pp. 105-113, 2010.

BiB
TeX
Algebraic pseudorandom functions with improved efficiency from the augmented cascade.
Dan Boneh, Hart William Montgomery, Ananth Raghunathan.
In proc. CCS, pp. 131-140, 2010.

BiB
TeX
Robust fingerprinting codes: a near optimal construction.
Dan Boneh, Aggelos Kiayias, Hart William Montgomery.
In proc. Digital Rights Management Workshop, pp. 3-12, 2010.

BiB
TeX
How to distribute antidote to control epidemics.
Christian Borgs, Jennifer T. Chayes, Ayalvadi Ganesh, Amin Saberi.
In Random Struct. Algorithms, vol. 37, no. 2, pp. 204-222, 2010.

BiB
TeX
Webseclab Security Education Workbench.
Elie Bursztein, Baptiste Gourdin, Celine Fabry, Jason Bau, Gustav Rydstedt, Hristo Bojinov, Dan Boneh, John C. Mitchell.
In proc. CSET, 2010.

BiB
TeX
Vertex Sparsifiers and Abstract Rounding Algorithms.
Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra.
In proc. FOCS, pp. 265-274, 2010.

BiB
TeX
l22 Spreading Metrics for Vertex Ordering Problems.
Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao.
In Algorithmica, vol. 56, no. 4, pp. 577-604, 2010.

BiB
TeX
Local Global Tradeoffs in Metric Embeddings.
Moses Charikar, Konstantin Makarychev, Yury Makarychev.
In SIAM J. Comput., vol. 39, no. 6, pp. 2487-2512, 2010.

BiB
TeX
Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.
Chandra Chekuri, Jan Vondrák, Rico Zenklusen.
In proc. FOCS, pp. 575-584, 2010.

BiB
TeX
Designing Network Protocols for Good Equilibria.
Ho-Lin Chen, Tim Roughgarden, Gregory Valiant.
In SIAM J. Comput., vol. 39, no. 5, pp. 1799-1832, 2010.

BiB
TeX
Pricing for Fairness: Distributed Resource Allocation for Multiple Objectives.
Sung-woo Cho, Ashish Goel.
In Algorithmica, vol. 57, no. 4, pp. 873-892, 2010.

BiB
TeX
Liquidity in Credit Networks: A Little Trust Goes a Long Way.
Pranav Dandekar, Ashish Goel, Ramesh Govindan, Ian Post.
In proc. NetEcon, pp. 1:1, 2010.

BiB
TeX
On Learning Algorithms for Nash Equilibria.
Constantinos Daskalakis, Rafael M. Frongillo, Christos H. Papadimitriou, George Pierrakos, Gregory Valiant.
In proc. SAGT, pp. 114-125, 2010.

BiB
TeX
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions.
Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan.
In proc. CCC, pp. 211-222, 2010.

BiB
TeX
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.
Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 533-542, 2010.

BiB
TeX
Secure, Consumer-Friendly Web Authentication and Payments with a Phone.
Ben Dodson, Debangsu Sengupta, Dan Boneh, Monica S. Lam.
In proc. MobiCASE, pp. 17-38, 2010.

BiB
TeX
The Submodular Welfare Problem with Demand Queries.
Uriel Feige, Jan Vondrák.
In Theory Comput., vol. 6, no. 1, pp. 247-290, 2010.

BiB
TeX
Advertisement allocation for generalized second-pricing schemes.
Ashish Goel, Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi.
In Oper. Res. Lett., vol. 38, no. 6, pp. 571-576, 2010.

BiB
TeX
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk.
Ashish Goel, Ian Post.
In proc. FOCS, pp. 593-600, 2010.

BiB
TeX
Small subset queries and bloom filters using ternary associative memories, with applications.
Ashish Goel, Pankaj Gupta.
In proc. SIGMETRICS, pp. 143-154, 2010.

BiB
TeX
Perfect matchings in o(n log n) time in regular bipartite graphs.
Ashish Goel, Michael Kapralov, Sanjeev Khanna.
In proc. STOC, pp. 39-46, 2010.

BiB
TeX
Advertisement allocation for generalized second-pricing schemes.
Ashish Goel, Mohammad Mahdian, Hamid Nazerzadeh, Amin Saberi.
In Oper. Res. Lett., vol. 38, no. 6, pp. 571-576, 2010.

BiB
TeX
How to probe for an extreme value.
Ashish Goel, Sudipto Guha, Kamesh Munagala.
In ACM Trans. Algorithms, vol. 7, no. 1, pp. 12:1-12:20, 2010.

BiB
TeX
Perfect matchings via uniform sampling in regular bipartite graphs.
Ashish Goel, Michael Kapralov, Sanjeev Khanna.
In ACM Trans. Algorithms, vol. 6, no. 2, pp. 27:1-27:13, 2010.

BiB
TeX
Partial exposure in large games.
Ronen Gradwohl, Omer Reingold.
In Games Econ. Behav., vol. 68, no. 2, pp. 602-613, 2010.

BiB
TeX
Universal One-Way Hash Functions via Inaccessible Entropy.
Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil P. Vadhan, Hoeteck Wee.
In proc. EUROCRYPT, pp. 616-637, 2010.

BiB
TeX
Efficiency improvements in constructing pseudorandom generators from one-way functions.
Iftach Haitner, Omer Reingold, Salil P. Vadhan.
In proc. STOC, pp. 437-446, 2010.

BiB
TeX
Efficiently learning mixtures of two Gaussians.
Adam Tauman Kalai, Ankur Moitra, Gregory Valiant.
In proc. STOC, pp. 553-562, 2010.

BiB
TeX
Subgraph sparsification and nearly optimal ultrasparsifiers.
Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng.
In proc. STOC, pp. 57-66, 2010.

BiB
TeX
Matroid matching: the power of local search.
Jon Lee, Maxim Sviridenko, Jan Vondrák.
In proc. STOC, pp. 369-378, 2010.

BiB
TeX
Submodular Maximization over Multiple Matroids via Generalized Exchange Properties.
Jon Lee, Maxim Sviridenko, Jan Vondrák.
In Math. Oper. Res., vol. 35, no. 4, pp. 795-806, 2010.

BiB
TeX
Design Paradigm for Robust Spin-Torque Transfer Magnetic RAM (STT MRAM) From Circuit/Architecture Perspective.
Jing Li, Patrick Ndai, Ashish Goel, Sayeef S. Salahuddin, Kaushik Roy.
In IEEE Trans. Very Large Scale Integr. Syst., vol. 18, no. 12, pp. 1710-1723, 2010.

BiB
TeX
The Limits of Two-Party Differential Privacy.
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan.
In proc. FOCS, pp. 81-90, 2010.

BiB
TeX
Accurate characterization of random process variations using a robust low-voltage high-sensitivity sensor featuring replica-bias circuit.
Mesut Meterelliyoz, Ashish Goel, Jaydeep P. Kulkarni, Kaushik Roy.
In proc. ISSCC, pp. 186-187, 2010.

BiB
TeX
Settling the Polynomial Learnability of Mixtures of Gaussians.
Ankur Moitra, Gregory Valiant.
In proc. FOCS, pp. 93-102, 2010.

BiB
TeX
The spread of innovations in social networks.
Andrea Montanari, Amin Saberi.
In Proc. Natl. Acad. Sci. USA, vol. 107, no. 47, pp. 20196-20201, 2010.

BiB
TeX
Data-dependant sense-amplifier flip-flop for low power applications.
Farshad Moradi, Charles Augustine, Ashish Goel, Georgios Karakonstantis, Tuan Vu Cao, Dag T. Wisland, Hamid Mahmoodi, Kaushik Roy.
In proc. CICC, pp. 1-4, 2010.

BiB
TeX
A Scalable Circuit-Architecture Co-Design to Improve Memory Yield for High-Performance Processors.
Patrick Ndai, Ashish Goel, Kaushik Roy.
In IEEE Trans. Very Large Scale Integr. Syst., vol. 18, no. 8, pp. 1209-1219, 2010.

BiB
TeX
A New Look at Selfish Routing.
Christos H. Papadimitriou, Gregory Valiant.
In proc. ICS, pp. 178-187, 2010.

BiB
TeX
Reliable Location-Based Services from Radio Navigation Systems.
Di Qiu, Dan Boneh, Sherman C. Lo, Per K. Enge.
In Sensors, vol. 10, no. 12, pp. 11369-11389, 2010.

BiB
TeX
Similarity search and locality sensitive hashing using ternary content addressable memories.
Rajendra Shinde, Ashish Goel, Pankaj Gupta, Debojyoti Dutta.
In proc. SIGMOD Conference, pp. 375-386, 2010.

BiB
TeX
Foreword.
Friedrich C. Simmel, Ashish Goel.
In Nat. Comput., vol. 9, no. 1, pp. 95-96, 2010.

BiB
TeX
A randomized embedding algorithm for trees.
Benny Sudakov, Jan Vondrák.
In Comb., vol. 30, no. 4, pp. 445-470, 2010.

BiB
TeX
Adnostic: Privacy Preserving Targeted Advertising.
Vincent Toubiana, Arvind Narayanan, Dan Boneh, Helen Nissenbaum, Solon Barocas.
In proc. NDSS, 2010.

BiB
TeX
Braess's Paradox in large random graphs.
Gregory Valiant, Tim Roughgarden.
In Random Struct. Algorithms, vol. 37, no. 4, pp. 495-515, 2010.