Publications of the Stanford Theory Group

2020
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.
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.
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.
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.
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.
Assignment Mechanisms Under Distributional Constraints.
Itai Ashlagi, Amin Saberi, Ali Shameli.
In Oper. Res., vol. 68, no. 2, pp. 467-479, 2020.
Near-optimal Approximate Discrete and Continuous Submodular Function Minimization.
Brian Axelrod, Yang P. Liu, Aaron Sidford.
In proc. SODA, pp. 837-853, 2020.
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.
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.
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.
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.
Constant-factor approximation of near-linear edit distance in near-linear time.
Joshua Brakensiek, Aviad Rubinstein.
In proc. STOC, pp. 685-698, 2020.
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.
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.
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.
Unconditional Lower Bounds for Adaptive Massively Parallel Computation.
Moses Charikar, Weiyun Ma, Li-Yang Tan.
In proc. SPAA, pp. 141-151, 2020.
Adaptive Discrete Phase Retrieval.
Moses Charikar, Xian Wu, Yinyu Ye.
In proc. SOSA@SODA, pp. 47-56, 2020.
Unconditional Lower Bounds for Adaptive Massively Parallel Computation.
Moses Charikar, Weiyun Ma, Li-Yang Tan.
In proc. SPAA, pp. 141-151, 2020.
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.
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.
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.
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.
CoopStore: Optimizing Precomputed Summaries for Aggregation.
Edward Gan, Peter Bailis, Moses Charikar.
In Proc. VLDB Endow., vol. 13, no. 11, pp. 2174-2187, 2020.
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.
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.
Continuous Credit Networks and Layer 2 Blockchains: Monotonicity and Sampling.
Ashish Goel, Geoffrey Ramseyer.
In proc. EC, pp. 613-635, 2020.
Does preprocessing help in fast sequence comparisons?
Elazar Goldenberg, Aviad Rubinstein, Barna Saha.
In proc. STOC, pp. 657-670, 2020.
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.
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.
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.
Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.
Oliver Hinder, Aaron Sidford, Nimit Sharad Sohoni.
In proc. COLT, pp. 1894-1938, 2020.
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.
Sublinear Optimal Policy Value Estimation in Contextual Bandits.
Weihao Kong, Emma Brunskill, Gregory Valiant.
In proc. AISTATS, pp. 4377-4387, 2020.
Retrieving Top Weighted Triangles in Graphs.
Raunak Kumar, Paul Liu, Moses Charikar, Austin R. Benson.
In proc. WSDM, pp. 295-303, 2020.
A polynomial lower bound on adaptive complexity of submodular maximization.
Wenzheng Li, Paul Liu, Jan Vondrák.
In proc. STOC, pp. 140-152, 2020.
Bounded-Leakage Differential Privacy.
Katrina Ligett, Charlotte Peale, Omer Reingold.
In proc. FORC, pp. 10:1-10:20, 2020.
Faster energy maximization for faster maximum flow.
Yang P. Liu, Aaron Sidford.
In proc. STOC, pp. 803-814, 2020.
Fooling Gaussian PTFs via local hyperconcentration.
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 1170-1183, 2020.
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.
Liquidity in Credit Networks with Constrained Agents.
Geoffrey Ramseyer, Ashish Goel, David Mazières.
In proc. WWW, pp. 2099-2108, 2020.
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.
Through the lens of a passionate theoretician.
Omer Reingold.
In Commun. ACM, vol. 63, no. 3, pp. 25-27, 2020.
Linear-time Erasure List-decoding of Expander Codes.
Noga Ron-Zewi, Mary Wootters, Gilles Zémor.
In proc. ISIT, pp. 379-383, 2020.
Optimal Single-Choice Prophet Inequalities from Samples.
Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg.
In proc. ITCS, pp. 60:1-60:10, 2020.
Reducing approximate Longest Common Subsequence to approximate Edit Distance.
Aviad Rubinstein, Zhao Song.
In proc. SODA, pp. 1591-1600, 2020.
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.
Remote Side-Channel Attacks on Anonymous Transactions.
Florian Tramèr, Dan Boneh, Kenny Paterson.
In proc. USENIX Security Symposium, pp. 2739-2756, 2020.
An Airdrop that Preserves Recipient Privacy.
Riad S. Wahby, Dan Boneh, Christopher Jeffrey, Joseph Poon.
In proc. Financial Cryptography, pp. 444-463, 2020.
List-Decodability of Structured Ensembles of Codes (Invited Talk).
Mary Wootters.
In proc. MFCS, pp. 3:1-3:5, 2020.
2019
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.
Competition in Ride-Hailing Markets.
AmirMahdi Ahmadinejad, Hamid Nazerzadeh, Amin Saberi, Nolan Skochdopole, Kane Sweeney.
In proc. WINE, pp. 333, 2019.
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.
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.
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.
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.
A Tight Analysis of Bethe Approximation for Permanent.
Nima Anari, Alireza Rezaei.
In proc. FOCS, pp. 1434-1445, 2019.
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.
Edge Weighted Online Windowed Matching.
Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, Chris Sholley.
In proc. EC, pp. 729-742, 2019.
Assignment Mechanisms under Distributional Constraints.
Itai Ashlagi, Amin Saberi, Ali Shameli.
In proc. SODA, pp. 229-240, 2019.
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.
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.
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.
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.
Stochastic Gradient Coding for Flexible Straggler Mitigation in Distributed Learning.
Rawad Bitar, Mary Wootters, Salim El Rouayheb.
In proc. ITW, pp. 1-5, 2019.
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.
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.
Post-quantum EPID Signatures from Symmetric Primitives.
Dan Boneh, Saba Eskandarian, Ben Fisch.
In proc. CT-RSA, pp. 251-271, 2019.
Technical perspective: Attacking cryptographic key exchange with precomputation.
Dan Boneh.
In Commun. ACM, vol. 62, no. 1, pp. 105, 2019.
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.
The One-Way Communication Complexity of Dynamic Time Warping Distance.
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang.
In proc. Symposium on Computational Geometry, pp. 16:1-16:15, 2019.
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.
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.
A Rank-1 Sketch for Matrix Multiplicative Weights.
Yair Carmon, John C. Duchi, Aaron Sidford, Kevin Tian.
In proc. COLT, pp. 589-623, 2019.
Variance Reduction for Matrix Games.
Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian.
In proc. NeurIPS, pp. 11377-11388, 2019.
Faster Matroid Intersection.
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, Sam Chiu-wai Wong.
In proc. FOCS, pp. 1146-1168, 2019.
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.
A General Framework for Symmetric Property Estimation.
Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. NeurIPS, pp. 12426-12436, 2019.
Efficient profile maximum likelihood for universal symmetric property estimation.
Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. STOC, pp. 780-791, 2019.
Hierarchical Clustering for Euclidean Data.
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, Grigory Yaroslavtsev.
In proc. AISTATS, pp. 2721-2730, 2019.
Multi-resolution Hashing for Fast Pairwise Summations.
Moses Charikar, Paris Siminelakis.
In proc. FOCS, pp. 769-792, 2019.
A General Framework for Symmetric Property Estimation.
Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. NeurIPS, pp. 12426-12436, 2019.
Hierarchical Clustering better than Average-Linkage.
Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh.
In proc. SODA, pp. 2291-2304, 2019.
Efficient profile maximum likelihood for universal symmetric property estimation.
Moses Charikar, Kirankumar Shiragur, Aaron Sidford.
In proc. STOC, pp. 780-791, 2019.
Fine-grained Complexity Meets IP = PSPACE.
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein.
In proc. SODA, pp. 1-20, 2019.
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.
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.
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.
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.
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.
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.
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate.
Vitaly Feldman, Jan Vondrák.
In proc. COLT, pp. 1270-1279, 2019.
Tracking and Improving Information in the Service of Fairness.
Sumegha Garg, Michael P. Kim, Omer Reingold.
In proc. EC, pp. 809-824, 2019.
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.
Near Optimal Methods for Minimizing Convex Functions with Lipschitz $p$-th Derivatives.
Alexander Gasnikov, Pavel E. Dvurechensky, Eduard A. 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.
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.
Markets Beyond Nash Welfare for Leontief Utilities.
Ashish Goel, Reyna Hulett, Benjamin Plaut.
In proc. WINE, pp. 340, 2019.
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.
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.
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.
A Surprising Density of Illusionable Natural Speech.
Melody Y. Guan, Gregory Valiant.
In proc. CogSci, pp. 1871, 2019.
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.
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.
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.
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.
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG.
Yujia Jin, Aaron Sidford.
In proc. NeurIPS, pp. 3863-3873, 2019.
Falcon - A Flexible Architecture For Accelerating Cryptography.
Kevin Kiningham, Philip Levis, Mark Anderson, Dan Boneh, Mark Horowitz, Maurice Shih.
In proc. MASS, pp. 136-144, 2019.
Lifted Multiplicity Codes and the Disjoint Repair Group Property.
Ray Li, Mary Wootters.
In proc. APPROX-RANDOM, pp. 38:1-38:18, 2019.
Parallel Reachability in Almost Linear Work and Square Root Depth.
Yang P. Liu, Arun Jambulapati, Aaron Sidford.
In proc. FOCS, pp. 1664-1686, 2019.
Submodular Optimization in the MapReduce Model.
Paul Liu, Jan Vondrák.
In proc. SOSA@SODA, pp. 18:1-18:10, 2019.
Sampling Methods for Counting Temporal Motifs.
Paul Liu, Austin R. Benson, Moses Charikar.
In proc. WSDM, pp. 294-302, 2019.
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.
Pseudorandom generators for width-3 branching programs.
Raghu Meka, Omer Reingold, Avishay Tal.
In proc. STOC, pp. 626-637, 2019.
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.
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.
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.
Fooling polytopes.
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 614-625, 2019.
Embedded Index Coding.
Alexandra Porter, Mary Wootters.
In proc. ITW, pp. 1-5, 2019.
A Theory of Selective Prediction.
Mingda Qiao, Gregory Valiant.
In proc. COLT, pp. 2580-2594, 2019.
Hardness of Approximation Between P and NP
Aviad Rubinstein.
Published by ACM, 2019, isbn 978-1-94748-723-9.
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.
SETH vs Approximation.
Aviad Rubinstein, Virginia Vassilevska Williams.
In SIGACT News, vol. 50, no. 4, pp. 57-76, 2019.
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas.
Rocco A. Servedio, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 45:1-45:23, 2019.
Pseudorandomness for read-k DNF formulas.
Rocco A. Servedio, Li-Yang Tan.
In proc. SODA, pp. 621-638, 2019.
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.
Memory-sample tradeoffs for linear regression with small error.
Vatsal Sharan, Aaron Sidford, Gregory Valiant.
In proc. STOC, pp. 890-901, 2019.
Rehashing Kernel Evaluation in High Dimensions.
Paris Siminelakis, Kexin Rong, Peter Bailis, Moses Charikar, Philip Levis.
In proc. ICML, pp. 5789-5798, 2019.
Unconstraining Graph-Constrained Group Testing.
Bruce Spang, Mary Wootters.
In proc. APPROX-RANDOM, pp. 46:1-46:20, 2019.
Equivariant Transformer Networks.
Kai Sheng Tai, Peter Bailis, Gregory Valiant.
In proc. ICML, pp. 6086-6095, 2019.
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.
AdVersarial: Perceptual Ad Blocking meets Adversarial Machine Learning.
Florian Tramèr, Pascal Dupré, Gili Rusak, Giancarlo Pellegrino, Dan Boneh.
In proc. ACM Conference on Computer and Communications Security, pp. 2005-2021, 2019.
Slalom: Fast, Verifiable and Private Execution of Neural Networks in Trusted Hardware.
Florian Tramèr, Dan Boneh.
In proc. ICLR, 2019.
Adversarial Training and Robustness for Multiple Perturbations.
Florian Tramèr, Dan Boneh.
In proc. NeurIPS, pp. 5858-5868, 2019.
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.
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.
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 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.
Recovery Guarantees For Quadratic Tensors With Sparse Observations.
Hongyang Zhang, Vatsal Sharan, Moses Charikar, Yingyu Liang.
In proc. AISTATS, pp. 3322-3332, 2019.
Pruning based Distance Sketches with Provable Guarantees on Random Graphs.
Hongyang Zhang, Huacheng Yu, Ashish Goel.
In proc. WWW, pp. 2301-2311, 2019.
2018
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.
Diffusion, Seeding, and the Value of Network Information.
Mohammad Akbarpour, Suraj Malladi, Amin Saberi.
In proc. EC, pp. 641, 2018.
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.
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.
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.
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.
Planar Graph Perfect Matching Is in NC.
Nima Anari, Vijay V. Vazirani.
In proc. FOCS, pp. 650-661, 2018.
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.
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.
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.
Budget Feasible Procurement Auctions.
Nima Anari, Gagan Goel, Afshin Nikzad.
In Oper. Res., vol. 66, no. 3, pp. 637-652, 2018.
Optimal Deterministic Mechanisms for an Additive Buyer.
Moshe Babaioff, Noam Nisan, Aviad Rubinstein.
In proc. EC, pp. 429, 2018.
Efficient Density Evaluation for Smooth Kernels.
Arturs Backurs, Moses Charikar, Piotr Indyk, Paris Siminelakis.
In proc. FOCS, pp. 615-626, 2018.
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.
Generating Random Networks Without Short Cycles.
Mohsen Bayati, Andrea Montanari, Amin Saberi.
In Oper. Res., vol. 66, no. 5, pp. 1227-1246, 2018.
Compact Multi-signatures for Smaller Blockchains.
Dan Boneh, Manu Drijvers, Gregory Neven.
In proc. ASIACRYPT (2), pp. 435-464, 2018.
Verifiable Delay Functions.
Dan Boneh, Joseph Bonneau, Benedikt Bünz, Ben Fisch.
In proc. CRYPTO (1), pp. 757-788, 2018.
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.
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.
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.
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.
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.
Multi-commodity Flow with In-Network Processing.
Moses Charikar, Yonatan Naamad, Jennifer Rexford, X. Kelvin Zou.
In proc. ALGOCLOUD, pp. 73-101, 2018.
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.
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.
Improved pseudorandomness for unordered branching programs through local monotonicity.
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal.
In proc. STOC, pp. 363-375, 2018.
Hierarchical Clustering with Structural Constraints.
Vaggos Chatziafratis, Rad Niazadeh, Moses Charikar.
In proc. ICML, pp. 773-782, 2018.
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.
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.
Approximating the Spectrum of a Graph.
David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant.
In proc. KDD, pp. 1263-1271, 2018.
Generalization Bounds for Uniformly Stable Algorithms.
Vitaly Feldman, Jan Vondrák.
In proc. NeurIPS, pp. 9770-9780, 2018.
99% Revenue via Enhanced Competition.
Michal Feldman, Ophir Friedler, Aviad Rubinstein.
In proc. EC, pp. 443-460, 2018.
A Spectral View of Adversarially Robust Features.
Shivam Garg, Vatsal Sharan, Brian Hu Zhang, Gregory Valiant.
In proc. NeurIPS, pp. 10159-10169, 2018.
Markets for Public Decision-Making.
Nikhil Garg, Ashish Goel, Benjamin Plaut.
In proc. WINE, pp. 445, 2018.
Relating Metric Distortion and Fairness of Social Choice Rules.
Ashish Goel, Reyna Hulett, Anilesh K. Krishnaswamy.
In proc. NetEcon@SIGMETRICS, pp. 4:1, 2018.
Implementing the Lexicographic Maxmin Bargaining Solution.
Ashish Goel, Anilesh K. Krishnaswamy.
In proc. WINE, pp. 449-450, 2018.
Exploiting Numerical Sparsity for Efficient Learning : Faster Eigenvector Computation and Regression.
Neha Gupta, Aaron Sidford.
In proc. NeurIPS, pp. 5274-5283, 2018.
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria.
Mika Göös, Aviad Rubinstein.
In proc. FOCS, pp. 397-403, 2018.
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.
Linear-time list recovery of high-rate expander codes.
Brett Hemenway, Mary Wootters.
In Inf. Comput., vol. 261, no. Part, pp. 202-218, 2018.
Recovering Structured Probability Matrices.
Qingqing Huang, Sham M. Kakade, Weihao Kong, Gregory Valiant.
In proc. ITCS, pp. 46:1-46:14, 2018.
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.
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.
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.
Efficient Õ(n/) Spectral Sketches for the Laplacian and its Pseudoinverse.
Arun Jambulapati, Aaron Sidford.
In proc. SODA, pp. 2487-2503, 2018.
Fairness Through Computationally-Bounded Awareness.
Michael P. Kim, Omer Reingold, Guy N. Rothblum.
In proc. NeurIPS, pp. 4847-4857, 2018.
Estimating Learnability in the Sublinear Data Regime.
Weihao Kong, Gregory Valiant.
In proc. NeurIPS, pp. 5460-5469, 2018.
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.
Efficient Convex Optimization with Membership Oracles.
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala.
In proc. COLT, pp. 1292-1294, 2018.
Improved List-Decodability of Random Linear Binary Codes.
Ray Li, Mary Wootters.
In proc. APPROX-RANDOM, pp. 50:1-50:19, 2018.
A Data Prism: Semi-verified learning in the small-alpha regime.
Michela Meister, Gregory Valiant.
In proc. COLT, pp. 1530-1546, 2018.
Incremental Deterministic Public-Key Encryption.
Ilya Mironov, Omkant Pandey, Omer Reingold, Gil Segev.
In J. Cryptol., vol. 31, no. 1, pp. 134-161, 2018.
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.
Stability of the Lanczos Method for Matrix Function Approximation.
Cameron Musco, Christopher Musco, Aaron Sidford.
In proc. SODA, pp. 1605-1624, 2018.
Prophet Inequalities vs. Approximating Optimum Online.
Rad Niazadeh, Amin Saberi, Ali Shameli.
In proc. WINE, pp. 356-374, 2018.
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.
Fast Blind MIMO Decoding through Vertex Hopping.
Jonathan Perlstein, Thomas R. Dean, Mary Wootters, Andrea Goldsmith.
In proc. ACSSC, pp. 148-154, 2018.
Load-Balanced Fractional Repetition Codes.
Alexandra Porter, Shashwat Silas, Mary Wootters.
In proc. ISIT, pp. 2072-2076, 2018.
Learning Discrete Distributions from Untrusted Batches.
Mingda Qiao, Gregory Valiant.
In proc. ITCS, pp. 47:1-47:20, 2018.
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.
On Taking Advantage of Multiple Requests in Error Correcting Codes.
Prasanna Ramakrishnan, Mary Wootters.
In proc. ISIT, pp. 1340-1344, 2018.
Efficient Batch Verification for UP.
Omer Reingold, Guy N. Rothblum, Ron D. Rothblum.
In proc. Computational Complexity Conference, pp. 22:1-22:23, 2018.
Computing Exact Minimum Cuts Without Knowing the Graph.
Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg.
In proc. ITCS, pp. 39:1-39:16, 2018.
Hardness of approximate nearest neighbor search.
Aviad Rubinstein.
In proc. STOC, pp. 1260-1268, 2018.
Inapproximability of Nash Equilibrium.
Aviad Rubinstein.
In SIAM J. Comput., vol. 47, no. 3, pp. 917-959, 2018.
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.
Average-radius list-recoverability of random linear codes.
Atri Rudra, Mary Wootters.
In proc. SODA, pp. 644-662, 2018.
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.
Prediction with a short memory.
Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant.
In proc. STOC, pp. 1074-1087, 2018.
Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow.
Aaron Sidford, Kevin Tian.
In proc. FOCS, pp. 922-933, 2018.
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.
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.
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.
Sketching Linear Classifiers over Data Streams.
Kai Sheng Tai, Vatsal Sharan, Peter Bailis, Gregory Valiant.
In proc. SIGMOD Conference, pp. 757-772, 2018.
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.
Creating Crowdsourced Research Talks at Scale.
Rajan Vaish, Shirish Goyal, Amin Saberi, Sharad Goel.
In proc. WWW, pp. 1-11, 2018.
Local Density Estimation in High Dimensions.
Xian Wu, Moses Charikar, Vishnu Natchu.
In proc. ICML, pp. 5293-5301, 2018.
2017
Distributed PCP Theorems for Hardness of Approximation in P.
Amir Abboud, Aviad Rubinstein, R. Ryan Williams.
In proc. FOCS, pp. 25-36, 2017.
Information Aggregation in Overlapping Generations.
Mohammad Akbarpour, Amin Saberi, Ali Shameli.
In proc. WINE, pp. 401, 2017.
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.
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.
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.
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.
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.
A generalization of permanent inequalities and applications in counting and optimization.
Nima Anari, Shayan Oveis Gharan.
In proc. STOC, pp. 384-396, 2017.
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.
Min-Cost Bipartite Perfect Matching with Delays.
Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul M. Makhijani, Yuyi Wang, Roger Wattenhofer.
In proc. APPROX-RANDOM, pp. 1:1-1:20, 2017.
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.
Communication complexity of approximate Nash equilibria.
Yakov Babichenko, Aviad Rubinstein.
In proc. STOC, pp. 878-889, 2017.
The limitations of optimization from samples.
Eric Balkanski, Aviad Rubinstein, Yaron Singer.
In proc. STOC, pp. 1016-1027, 2017.
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.
Repairing multiple failures for scalar MDS codes.
Burak Bartan, Mary Wootters.
In proc. Allerton, pp. 1145-1152, 2017.
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.
Lattice-Based DAPS and Generalizations: Self-enforcement in Signature Schemes.
Dan Boneh, Sam Kim, Valeria Nikolaenko.
In proc. ACNS, pp. 457-477, 2017.
Surnaming Schemes, Fast Verification, and Applications to SGX Technology.
Dan Boneh, Shay Gueron.
In proc. CT-RSA, pp. 149-164, 2017.
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.
Private Puncturable PRFs from Standard Lattice Assumptions.
Dan Boneh, Sam Kim, Hart William Montgomery.
In proc. EUROCRYPT (1), pp. 415-445, 2017.
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.
Constraining Pseudorandom Functions Privately.
Dan Boneh, Kevin Lewi, David J. Wu.
In proc. Public Key Cryptography (2), pp. 494-524, 2017.
Constrained Keys for Invertible Pseudorandom Functions.
Dan Boneh, Sam Kim, David J. Wu.
In proc. TCC (1), pp. 237-263, 2017.
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.
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.
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.
"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.
Subquadratic submodular function minimization.
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong.
In proc. STOC, pp. 1220-1231, 2017.
Learning from untrusted data.
Moses Charikar, Jacob Steinhardt, Gregory Valiant.
In proc. STOC, pp. 47-60, 2017.
Hashing-Based-Estimators for Kernel Density in High Dimensions.
Moses Charikar, Paris Siminelakis.
In proc. FOCS, pp. 1032-1043, 2017.
Local Guarantees in Graph Cuts and Clustering.
Moses Charikar, Neha Gupta, Roy Schwartz.
In proc. IPCO, pp. 136-147, 2017.
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics.
Moses Charikar, Vaggos Chatziafratis.
In proc. SODA, pp. 841-854, 2017.
Learning from untrusted data.
Moses Charikar, Jacob Steinhardt, Gregory Valiant.
In proc. STOC, pp. 47-60, 2017.
Stability and Recovery for Independence Systems.
Vaggos Chatziafratis, Tim Roughgarden, Jan Vondrák.
In proc. ESA, pp. 26:1-26:15, 2017.
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.
Settling the Query Complexity of Non-Adaptive Junta Testing.
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie.
In proc. Computational Complexity Conference, pp. 26:1-26:19, 2017.
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.
Quantum Operating Systems.
Henry Corrigan-Gibbs, David J. Wu, Dan Boneh.
In proc. HotOS, pp. 76-81, 2017.
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics.
Henry Corrigan-Gibbs, Dan Boneh.
In proc. NSDI, pp. 259-282, 2017.
Blind Joint MIMO Channel Estimation and Decoding.
Thomas R. Dean, Mary Wootters, Andrea Goldsmith.
In proc. GLOBECOM, pp. 1-6, 2017.
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.
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.
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.
Sequential Deliberation for Social Choice.
Brandon Fain, Ashish Goel, Kamesh Munagala, Sukolsak Sakshuwong.
In proc. WINE, pp. 177-190, 2017.
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.
IRON: Functional Encryption using Intel SGX.
Ben Fisch, Dhinakaran Vinayagamurthy, Dan Boneh, Sergey Gorbunov.
In proc. ACM Conference on Computer and Communications Security, pp. 765-782, 2017.
Locality via Partially Lifted Codes.
S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters.
In proc. APPROX-RANDOM, pp. 43:1-43:17, 2017.
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.
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.
Repairing Reed-Solomon Codes.
Venkatesan Guruswami, Mary Wootters.
In IEEE Trans. Inf. Theory, vol. 63, no. 9, pp. 5684-5698, 2017.
Local List Recovery of High-Rate Tensor Codes & Applications.
Brett Hemenway, Noga Ron-Zewi, Mary Wootters.
In proc. FOCS, pp. 204-215, 2017.
Limitations of piggybacking codes with low substriping.
Reyna Hulett, Mary Wootters.
In proc. Allerton, pp. 1131-1138, 2017.
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.
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.
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.
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.
T/Key: Second-Factor Authentication From Secure Hash Chains.
Dmitry Kogan, Nathan Manohar, Dan Boneh.
In proc. ACM Conference on Computer and Communications Security, pp. 983-999, 2017.
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.
Inapproximability of VC Dimension and Littlestone's Dimension.
Pasin Manurangsi, Aviad Rubinstein.
In proc. COLT, pp. 1432-1460, 2017.
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.
Estimating the unseen from multiple populations.
Aditi Raghunathan, Gregory Valiant, James Zou.
In proc. ICML, pp. 2855-2863, 2017.
When Are Welfare Guarantees Robust?.
Tim Roughgarden, Inbal Talgam-Cohen, Jan Vondrák.
In proc. APPROX-RANDOM, pp. 22:1-22:23, 2017.
Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder.
Aviad Rubinstein.
In proc. ICALP, pp. 77:1-77:13, 2017.
Detecting communities is Hard (And Counting Them is Even Harder).
Aviad Rubinstein.
In proc. ITCS, pp. 42:1-42:13, 2017.
Combinatorial Prophet Inequalities.
Aviad Rubinstein, Sahil Singla.
In proc. SODA, pp. 1671-1687, 2017.
Sorting from Noisier Samples.
Aviad Rubinstein, Shai Vardi.
In proc. SODA, pp. 960-972, 2017.
Settling the complexity of computing approximate two-player Nash equilibria.
Aviad Rubinstein.
In SIGecom Exch., vol. 15, no. 2, pp. 45-49, 2017.
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time.
Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 813-823, 2017.
Fooling Intersections of Low-Weight Halfspaces.
Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 824-835, 2017.
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.
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.
Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use.
Vatsal Sharan, Gregory Valiant.
In proc. ICML, pp. 3095-3104, 2017.
Learning Overcomplete HMMs.
Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant.
In proc. NIPS, pp. 940-949, 2017.
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.
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.
Learning Populations of Parameters.
Kevin Tian, Weihao Kong, Gregory Valiant.
In proc. NIPS, pp. 5778-5787, 2017.
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.
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.
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.
Trust but Verify: Auditing the Secure Internet of Things.
Judson Wilson, Riad S. Wahby, Henry Corrigan-Gibbs, Dan Boneh, Philip Levis, Keith Winstein.
In proc. MobiSys, pp. 464-474, 2017.
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics.
Yuchen Zhang, Percy Liang, Moses Charikar.
In proc. COLT, pp. 1980-2022, 2017.
2016
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.
Euclidean movement minimization.
Nima Anari, MohammadAmin Fazli, Mohammad Ghodsi, MohammadAli Safari.
In J. Comb. Optim., vol. 32, no. 2, pp. 354-367, 2016.
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.
Can Almost Everybody be Almost Happy?
Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein.
In proc. ITCS, pp. 1-9, 2016.
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.
The Power of Optimization from Samples.
Eric Balkanski, Aviad Rubinstein, Yaron Singer.
In proc. NIPS, pp. 4017-4025, 2016.
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.
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.
On the Approximability of Sparse PCA.
Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein.
In proc. COLT, pp. 623-646, 2016.
On Approximating Target Set Selection.
Moses Charikar, Yonatan Naamad, Anthony Wirth.
In proc. APPROX-RANDOM, pp. 4:1-4:16, 2016.
Near-optimal small-depth lower bounds for small distance connectivity.
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan.
In proc. STOC, pp. 612-625, 2016.
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.
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.
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.
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.
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.
Routing under balance.
Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford.
In proc. STOC, pp. 598-611, 2016.
The Core of the Participatory Budgeting Problem.
Brandon Fain, Ashish Goel, Kamesh Munagala.
In proc. WINE, pp. 384-399, 2016.
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.
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.
Principal Component Projection Without Principal Component Analysis.
Roy Frostig, Cameron Musco, Christopher Musco, Aaron Sidford.
In proc. ICML, pp. 2349-2357, 2016.
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.
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.
Internet Economics [Guest editors' introduction].
Arpita Ghosh, Ashish Goel.
In IEEE Internet Comput., vol. 20, no. 1, pp. 8-10, 2016.
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.
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.
Repairing Reed-solomon codes.
Venkatesan Guruswami, Mary Wootters.
In proc. STOC, pp. 216-226, 2016.
Strategic Classification.
Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, Mary Wootters.
In proc. ITCS, pp. 111-122, 2016.
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.
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.
CESEL: Securing a Mote for 20 Years.
Kevin Kiningham, Mark Horowitz, Philip Levis, Dan Boneh.
In proc. EWSN, pp. 307-312, 2016.
Probabilistic Matrix Inspection and Group Scheduling.
Hooyeon Lee, Ashish Goel.
In proc. IJCAI, pp. 322-328, 2016.
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.
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. ACM Conference on Computer and Communications Security, pp. 981-992, 2016.
Personalized PageRank Estimation and Search: A Bidirectional Approach.
Peter Lofgren, Siddhartha Banerjee, Ashish Goel.
In proc. WSDM, pp. 163-172, 2016.
Special Issue: APPROX-RANDOM 2015: Guest Editors' Foreword.
Nicole Megow, Mary Wootters.
In Theory Comput., vol. 12, no. 1, pp. 1-3, 2016.
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.
On the Complexity of Dynamic Mechanism Design.
Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein.
In proc. SODA, pp. 1458-1475, 2016.
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.
Adaptive Condorcet-Based Stopping Rules Can Be Efficient.
Omer Reingold, Nina Narodytska.
In proc. ECAI, pp. 1704-1705, 2016.
Constant-round interactive proofs for delegating computation.
Omer Reingold, Guy N. Rothblum, Ron D. Rothblum.
In proc. STOC, pp. 49-62, 2016.
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.
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria.
Aviad Rubinstein.
In proc. FOCS, pp. 258-265, 2016.
On the Computational Complexity of Optimal Simple Mechanisms.
Aviad Rubinstein.
In proc. ITCS, pp. 21-28, 2016.
Beyond matroids: secretary problem and prophet inequality with general constraints.
Aviad Rubinstein.
In proc. STOC, pp. 324-332, 2016.
Incentive Compatibility of Bitcoin Mining Pool Reward Functions.
Okke Schrijvers, Joseph Bonneau, Dan Boneh, Tim Roughgarden.
In proc. Financial Cryptography, pp. 477-498, 2016.
Memory, Communication, and Statistical Queries.
Jacob Steinhardt, Gregory Valiant, Stefan Wager.
In proc. COLT, pp. 1490-1516, 2016.
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction.
Jacob Steinhardt, Gregory Valiant, Moses Charikar.
In proc. NIPS, pp. 4439-4447, 2016.
Instance optimal learning of discrete distributions.
Gregory Valiant, Paul Valiant.
In proc. STOC, pp. 142-155, 2016.
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.
Approximate Personalized PageRank on Dynamic Graphs.
Hongyang Zhang, Peter Lofgren, Ashish Goel.
In proc. KDD, pp. 1315-1324, 2016.
2015
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.
Approximation Algorithms for Computing Maximin Share Allocations.
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi.
In proc. ICALP (1), pp. 39-51, 2015.
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP.
Nima Anari, Shayan Oveis Gharan.
In proc. FOCS, pp. 20-39, 2015.
Label optimal regret bounds for online local learning.
Pranjal Awasthi, Moses Charikar, Kevin A. Lai, Andrej Risteski.
In proc. COLT, pp. 150-166, 2015.
The Hardness of Approximation of Euclidean k-Means.
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop.
In proc. Symposium on Computational Geometry, pp. 754-767, 2015.
Relax, No Need to Round: Integrality of Clustering Formulations.
Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel Ward.
In proc. ITCS, pp. 191-200, 2015.
Testing Closeness With Unequal Sized Samples.
Bhaswar B. Bhattacharya, Gregory Valiant.
In proc. NIPS, pp. 2611-2619, 2015.
Learning Circuits with few Negations.
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 512-527, 2015.
Approximating Boolean Functions with Depth-2 Circuits.
Eric Blais, Li-Yang Tan.
In SIAM J. Comput., vol. 44, no. 6, pp. 1583-1600, 2015.
Hosting Services on an Untrusted Cloud.
Dan Boneh, Divya Gupta, Ilya Mironov, Amit Sahai.
In proc. EUROCRYPT (2), pp. 404-436, 2015.
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.
Bypassing Worst Case Analysis: Tensor Decomposition and Clustering (Invited Talk).
Moses Samson Charikar.
In proc. FSTTCS, pp. 1, 2015.
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.
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.
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.
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.
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.
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.
Provisions: Privacy-preserving Proofs of Solvency for Bitcoin Exchanges.
Gaby G. Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark, Dan Boneh.
In proc. ACM Conference on Computer and Communications Security, pp. 720-731, 2015.
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.
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.
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.
Algorithmic Signaling of Features in Auction Design.
Shaddin Dughmi, Nicole Immorlica, Ryan O'Donnell, Li-Yang Tan.
In proc. SAGT, pp. 150-162, 2015.
Limitations of randomized mechanisms for combinatorial auctions.
Shaddin Dughmi, Jan Vondrák.
In Games Econ. Behav., vol. 92, pp. 370-400, 2015.
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.
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.
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.
Team Formation Dynamics: A Study Using Online Learning Data.
Milad Eftekhar, Farnaz Ronaghi, Amin Saberi.
In proc. COSN, pp. 257-267, 2015.
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions.
Vitaly Feldman, Jan Vondrák.
In proc. FOCS, pp. 923-942, 2015.
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.
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.
Connectivity in Random Forests and Credit Networks.
Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang.
In proc. SODA, pp. 2037-2048, 2015.
A Note on Modeling Retweet Cascades on Twitter.
Ashish Goel, Kamesh Munagala, Aneesh Sharma, Hongyang Zhang.
In proc. WAW, pp. 119-131, 2015.
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.
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.
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.
Linear-Time List Recovery of High-Rate Expander Codes.
Brett Hemenway, Mary Wootters.
In proc. ICALP (1), pp. 701-712, 2015.
Local correctability of expander codes.
Brett Hemenway, Rafail Ostrovsky, Mary Wootters.
In Inf. Comput., vol. 243, pp. 178-190, 2015.
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming.
Yin Tat Lee, Aaron Sidford.
In proc. FOCS, pp. 230-249, 2015.
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.
Bidirectional PageRank Estimation: From Average-Case to Worst-Case.
Peter Lofgren, Siddhartha Banerjee, Ashish Goel.
In proc. WAW, pp. 164-176, 2015.
Robust Probabilistic Inference.
Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz.
In proc. SODA, pp. 449-460, 2015.
CCFI: Cryptographically Enforced Control Flow Integrity.
Ali José Mashtizadeh, Andrea Bittau, Dan Boneh, David Mazières.
In proc. ACM Conference on Computer and Communications Security, pp. 941-951, 2015.
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.
Sperner's Colorings, Hypergraph Labeling Problems and Fair Division.
Maryam Mirzakhani, Jan Vondrák.
In proc. SODA, pp. 873-886, 2015.
Lazier Than Lazy Greedy.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, Andreas Krause.
In proc. AAAI, pp. 1812-1818, 2015.
An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 1030-1048, 2015.
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.
Approximability of Adaptive Seeding under Knapsack Constraints.
Aviad Rubinstein, Lior Seeman, Yaron Singer.
In proc. EC, pp. 797-814, 2015.
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity.
Aviad Rubinstein, S. Matthew Weinberg.
In proc. EC, pp. 377-394, 2015.
Inapproximability of Nash Equilibrium.
Aviad Rubinstein.
In proc. STOC, pp. 409-418, 2015.
The complexity of simplicity in mechanism design.
Aviad Rubinstein.
In SIGecom Exch., vol. 14, no. 2, pp. 41-43, 2015.
It'll Probably Work Out: Improved List-Decoding Through Random Operations.
Atri Rudra, Mary Wootters.
In proc. ITCS, pp. 287-296, 2015.
Adaptivity Helps for Testing Juntas.
Rocco A. Servedio, Li-Yang Tan, John Wright.
In proc. Computational Complexity Conference, pp. 264-279, 2015.
Information-theoretic lower bounds for convex optimization with erroneous oracles.
Yaron Singer, Jan Vondrák.
In proc. NIPS, pp. 3204-3212, 2015.
Optimal approximation for submodular and supermodular optimization with bounded curvature.
Maxim Sviridenko, Jan Vondrák, Justin Ward.
In proc. SODA, pp. 1134-1148, 2015.
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
On Simplex Pivoting Rules and Complexity Theory.
Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein.
In proc. IPCO, pp. 13-24, 2014.
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.
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.
Learning Polynomials with Neural Networks.
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang.
In proc. ICML, pp. 1908-1916, 2014.
Learning Sparse Polynomial Functions.
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang.
In proc. SODA, pp. 500-510, 2014.
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.
Fast algorithms for maximizing submodular functions.
Ashwinkumar Badanidiyuru, Jan Vondrák.
In proc. SODA, pp. 1497-1514, 2014.
Efficient Primal-Dual Graph Algorithms for MapReduce.
Bahman Bahmani, Ashish Goel, Kamesh Munagala.
In proc. WAW, pp. 59-78, 2014.
Multireference alignment using semidefinite programming.
Afonso S. Bandeira, Moses Charikar, Amit Singer, Andy Zhu.
In proc. ITCS, pp. 459-470, 2014.
Re-incentivizing discovery: mechanisms for partial-progress sharing in research.
Siddhartha Banerjee, Ashish Goel, Anilesh Kollagunta Krishnaswamy.
In proc. EC, pp. 149-166, 2014.
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.
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.
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability.
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan.
In proc. COLT, pp. 742-778, 2014.
Smoothed analysis of tensor decompositions.
Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan.
In proc. STOC, pp. 594-603, 2014.
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.
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.
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.
Bivariate Polynomials Modulo Composites and Their Applications.
Dan Boneh, Henry Corrigan-Gibbs.
In proc. ASIACRYPT (1), pp. 42-62, 2014.
Low Overhead Broadcast Encryption from Multilinear Maps.
Dan Boneh, Brent Waters, Mark Zhandry.
In proc. CRYPTO (1), pp. 206-223, 2014.
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation.
Dan Boneh, Mark Zhandry.
In proc. CRYPTO (1), pp. 480-499, 2014.
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.
Optimal Algorithms for Testing Closeness of Discrete Distributions.
Siu-on Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant.
In proc. SODA, pp. 1193-1203, 2014.
Online Bipartite Matching with Decomposable Weights.
Moses Charikar, Monika Henzinger, Huy L. Nguyen.
In proc. ESA, pp. 260-271, 2014.
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.
New Algorithms and Lower Bounds for Monotonicity Testing.
Xi Chen, Rocco A. Servedio, Li-Yang Tan.
In proc. FOCS, pp. 286-295, 2014.
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.
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.
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.
Optimal bounds on approximation of submodular and XOS functions by juntas.
Vitaly Feldman, Jan Vondrák.
In proc. ITA, pp. 1-10, 2014.
Disjoint Set Union with Randomized Linking.
Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan.
In proc. SODA, pp. 1005-1017, 2014.
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.
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.
Fault tolerance in large games.
Ronen Gradwohl, Omer Reingold.
In Games Econ. Behav., vol. 86, pp. 438-457, 2014.
A New Interactive Hashing Theorem.
Iftach Haitner, Omer Reingold.
In J. Cryptol., vol. 27, no. 1, pp. 109-138, 2014.
Fast matrix completion without the condition number.
Moritz Hardt, Mary Wootters.
In proc. COLT, pp. 638-678, 2014.
Tick Tock: Building Browser Red Pills from Timing Side Channels.
Grant Ho, Dan Boneh, Lucas Ballard, Niels Provos.
In proc. WOOT, 2014.
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.
Exchangeability and Realizability: De Finetti Theorems on Graphs.
T. S. Jayram, Jan Vondrák.
In proc. APPROX-RANDOM, pp. 762-778, 2014.
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.
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.
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.
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.
Crowdsourcing for Participatory Democracies: Efficient Elicitation of Social Choice Functions.
David Timothy Lee, Ashish Goel, Tanja Aitamurto, Hélène Landemore.
In proc. HCOMP, 2014.
Satisfiability and Evolution.
Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan.
In proc. FOCS, pp. 524-530, 2014.
FAST-PPR: scaling personalized pagerank estimation for large graphs.
Peter Lofgren, Siddhartha Banerjee, Ashish Goel, Seshadhri Comandur.
In proc. KDD, pp. 1436-1445, 2014.
Deterministic Coupon Collection and Better Strong Dispersers.
Raghu Meka, Omer Reingold, Yuan Zhou.
In proc. APPROX-RANDOM, pp. 872-884, 2014.
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.
Gyrophone: Recognizing Speech from Gyroscope Signals.
Yan Michalevsky, Dan Boneh, Gabi Nakibly.
In proc. USENIX Security Symposium, pp. 1053-1067, 2014.
New constructions of RIP matrices with fast multiplication and fewer rows.
Jelani Nelson, Eric Price, Mary Wootters.
In proc. SODA, pp. 1515-1528, 2014.
A Composition Theorem for Parity Kill Number.
Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan.
In proc. Computational Complexity Conference, pp. 144-154, 2014.
The complexity of fairness through equilibrium.
Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein.
In proc. EC, pp. 209-226, 2014.
Pseudorandom Graphs in Data Structures.
Omer Reingold, Ron D. Rothblum, Udi Wieder.
In proc. ICALP (1), pp. 943-954, 2014.
Every list-decodable code for high noise has abundant near-optimal rate puncturings.
Atri Rudra, Mary Wootters.
In proc. STOC, pp. 764-773, 2014.
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.
Is Submodularity Testable?
C. Seshadhri, Jan Vondrák.
In Algorithmica, vol. 69, no. 1, pp. 1-25, 2014.
Multiway cut, pairwise realizable distributions, and descending thresholds.
Ankit Sharma, Jan Vondrák.
In proc. STOC, pp. 724-733, 2014.
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.
An Automatic Inequality Prover and Instance Optimal Identity Testing.
Gregory Valiant, Paul Valiant.
In proc. FOCS, pp. 51-60, 2014.
2013
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.
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.
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.
Approximating Boolean Functions with Depth-2 Circuits.
Eric Blais, Li-Yang Tan.
In proc. Computational Complexity Conference, pp. 74-85, 2013.
Hypercontractivity Via the Entropy Method.
Eric Blais, Li-Yang Tan.
In Theory Comput., vol. 9, pp. 889-896, 2013.
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.
Function-Private Subspace-Membership Encryption and Its Applications.
Dan Boneh, Ananth Raghunathan, Gil Segev.
In proc. ASIACRYPT (1), pp. 255-275, 2013.
Constrained Pseudorandom Functions and Their Applications.
Dan Boneh, Brent Waters.
In proc. ASIACRYPT (2), pp. 280-300, 2013.
Key Homomorphic PRFs and Their Applications.
Dan Boneh, Kevin Lewi, Hart William Montgomery, Ananth Raghunathan.
In proc. CRYPTO (1), pp. 410-428, 2013.
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.
Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World.
Dan Boneh, Mark Zhandry.
In proc. CRYPTO (2), pp. 361-379, 2013.
Quantum-Secure Message Authentication Codes.
Dan Boneh, Mark Zhandry.
In proc. EUROCRYPT, pp. 592-608, 2013.
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.
Ensuring high-quality randomness in cryptographic key generation.
Henry Corrigan-Gibbs, Wendy Mu, Dan Boneh, Bryan Ford.
In proc. ACM Conference on Computer and Communications Security, pp. 685-696, 2013.
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.
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.
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.
Communication Complexity of Combinatorial Auctions with Submodular Valuations.
Shahar Dobzinski, Jan Vondrák.
In proc. SODA, pp. 1205-1215, 2013.
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.
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.
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.
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.
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas.
Vitaly Feldman, Jan Vondrák.
In proc. FOCS, pp. 227-236, 2013.
Structure and learning of valuation functions.
Vitaly Feldman, Jan Vondrák.
In SIGecom Exch., vol. 12, no. 2, pp. 50-53, 2013.
OSS: Using Online Scanning Services for Censorship Circumvention.
David Fifield, Gabi Nakibly, Dan Boneh.
In proc. Privacy Enhancing Technologies, pp. 185-204, 2013.
On Variants of the Matroid Secretary Problem.
Shayan Oveis Gharan, Jan Vondrák.
In Algorithmica, vol. 67, no. 4, pp. 472-497, 2013.
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.
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.
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.
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.
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.
WTF: the who to follow service at Twitter.
Pankaj Gupta, Ashish Goel, Jimmy J. Lin, Aneesh Sharma, Dong Wang, Reza Zadeh.
In proc. WWW, pp. 505-514, 2013.
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.
Local Correctability of Expander Codes.
Brett Hemenway, Rafail Ostrovsky, Mary Wootters.
In proc. ICALP (1), pp. 540-551, 2013.
Online Submodular Welfare Maximization: Greedy is Optimal.
Michael Kapralov, Ian Post, Jan Vondrák.
In proc. SODA, pp. 1216-1225, 2013.
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.
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.
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems.
Yin Tat Lee, Aaron Sidford.
In proc. FOCS, pp. 147-156, 2013.
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.
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.
Privacy-preserving matrix factorization.
Valeria Nikolaenko, Stratis Ioannidis, Udi Weinsberg, Marc Joye, Nina Taft, Dan Boneh.
In proc. ACM Conference on Computer and Communications Security, pp. 801-812, 2013.
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.
A Composition Theorem for the Fourier Entropy-Influence Conjecture.
Ryan O'Donnell, Li-Yang Tan.
In proc. ICALP (1), pp. 780-791, 2013.
Pseudorandomness for Regular Branching Programs via Fourier Analysis.
Omer Reingold, Thomas Steinke, Salil P. Vadhan.
In proc. APPROX-RANDOM, pp. 655-670, 2013.
On the Average Sensitivity and Density of k-CNF Formulas.
Dominik Scheder, Li-Yang Tan.
In proc. APPROX-RANDOM, pp. 683-698, 2013.
Estimating the Unseen: Improved Estimators for Entropy and other Properties.
Paul Valiant, Gregory Valiant.
In proc. NIPS, pp. 2157-2165, 2013.
Symmetry and Approximability of Submodular Maximization Problems.
Jan Vondrák.
In SIAM J. Comput., vol. 42, no. 1, pp. 265-304, 2013.
Lower bounds for quantized matrix completion.
Mary Wootters, Yaniv Plan, Mark A. Davenport, Ewout van den Berg.
In proc. ISIT, pp. 296-300, 2013.
On the list decodability of random linear codes with large error rates.
Mary Wootters.
In proc. STOC, pp. 853-860, 2013.
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.
On the precision of social and information networks.
Reza Bosagh Zadeh, Ashish Goel, Kamesh Munagala, Aneesh Sharma.
In proc. COSN, pp. 63-74, 2013.
Dimension independent similarity computation.
Reza Bosagh Zadeh, Ashish Goel.
In J. Mach. Learn. Res., vol. 14, no. 1, pp. 1605-1626, 2013.
2012
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.
Computing on Authenticated Data.
Jae Hyun Ahn, Dan Boneh, Jan Camenisch, Susan Hohenberger, Abhi Shelat, Brent Waters.
In proc. TCC, pp. 1-20, 2012.
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.
Efficient distributed locality sensitive hashing.
Bahman Bahmani, Ashish Goel, Rajendra Shinde.
In proc. CIKM, pp. 2174-2178, 2012.
Partitioned multi-indexing: bringing order to social search.
Bahman Bahmani, Ashish Goel.
In proc. WWW, pp. 399-408, 2012.
On Quadratic Programming with a Ratio Objective.
Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan.
In proc. ICALP (1), pp. 109-120, 2012.
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.
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.
Pairing-Based Cryptography: Past, Present, and Future.
Dan Boneh.
In proc. ASIACRYPT, pp. 1, 2012.
Targeted malleability: homomorphic encryption for restricted computations.
Dan Boneh, Gil Segev, Brent Waters.
In proc. ITCS, pp. 350-366, 2012.
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.
HBIST: An approach towards zero external test cost.
Mayur Bubna, Kaushik Roy, Ashish Goel.
In proc. VTS, pp. 13-18, 2012.
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.
A Dependent LP-Rounding Approach for the k-Median Problem.
Moses Charikar, Shi Li.
In proc. ICALP (1), pp. 194-205, 2012.
Biased Assimilation, Homophily, and the Dynamics of Polarization - (Working Paper).
Pranav Dandekar, Ashish Goel, David Lee.
In proc. WINE, pp. 559, 2012.
Strategic formation of credit networks.
Pranav Dandekar, Ashish Goel, Michael P. Wellman, Bryce Wiedenbeck.
In proc. WWW, pp. 559-568, 2012.
Algorithmic Solutions for Envy-Free Cake Cutting.
Xiaotie Deng, Qi Qi, Amin Saberi.
In Oper. Res., vol. 60, no. 6, pp. 1461-1476, 2012.
The computational complexity of truthfulness in combinatorial auctions.
Shahar Dobzinski, Jan Vondrák.
In proc. EC, pp. 405-422, 2012.
From query complexity to computational complexity.
Shahar Dobzinski, Jan Vondrák.
In proc. STOC, pp. 1107-1116, 2012.
High-confidence near-duplicate image detection.
Wei Dong, Zhe Wang, Moses Charikar, Kai Li.
In proc. ICMR, pp. 1, 2012.
Fairness through awareness.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel.
In proc. ITCS, pp. 214-226, 2012.
Evading Censorship with Browser-Based Proxies.
David Fifield, Nate Hardison, Jonathan Ellithorpe, Emily Stark, Dan Boneh, Roger Dingledine, Phillip A. Porras.
In proc. Privacy Enhancing Technologies, pp. 239-258, 2012.
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.
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. ACM Conference on Computer and Communications Security, pp. 38-49, 2012.
Recovering simple signals.
Anna C. Gilbert, Brett Hemenway, Atri Rudra, Martin J. Strauss, Mary Wootters.
In proc. ITA, pp. 382-391, 2012.
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.
On the communication and streaming complexity of maximum bipartite matching.
Ashish Goel, Michael Kapralov, Sanjeev Khanna.
In proc. SODA, pp. 468-485, 2012.
A Game-Theoretic Model of Attention in Social Networks.
Ashish Goel, Farnaz Ronaghi.
In proc. WAW, pp. 78-92, 2012.
Triadic Consensus - A Randomized Algorithm for Voting in a Crowd.
Ashish Goel, David Lee.
In proc. WINE, pp. 434-447, 2012.
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.
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.
DNF Sparsification and a Faster Deterministic Counting Algorithm.
Parikshit Gopalan, Raghu Meka, Omer Reingold.
In proc. Computational Complexity Conference, pp. 126-135, 2012.
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.
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.
Disentangling Gaussians.
Adam Tauman Kalai, Ankur Moitra, Gregory Valiant.
In Commun. ACM, vol. 55, no. 2, pp. 113-120, 2012.
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.
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.
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.
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.
Dynamics of prisoner's dilemma and the evolution of cooperation on networks.
Vahideh H. Manshadi, Amin Saberi.
In proc. ITCS, pp. 227-235, 2012.
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.
Converting Online Algorithms to Local Computation Algorithms.
Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie.
In proc. ICALP (1), pp. 653-664, 2012.
Incremental Deterministic Public-Key Encryption.
Ilya Mironov, Omkant Pandey, Omer Reingold, Gil Segev.
In proc. EUROCRYPT, pp. 628-644, 2012.
Persistent OSPF Attacks.
Gabi Nakibly, Alex Kirshon, Dima Gonikman, Dan Boneh.
In proc. NDSS, 2012.
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.
The Case for Prefetching and Prevalidating TLS Server Certificates.
Emily Stark, Lin-Shung Huang, Dinesh Israni, Collin Jackson, Dan Boneh.
In proc. NDSS, 2012.
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.
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas.
Gregory Valiant.
In proc. FOCS, pp. 11-20, 2012.
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. ACM Conference on Computer and Communications Security, pp. 109-120, 2012.
2011
Fitting Tree Metrics: Hierarchical Clustering and Phylogeny.
Nir Ailon, Moses Charikar.
In SIAM J. Comput., vol. 40, no. 5, pp. 1275-1291, 2011.
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.
Only valuable experts can be valued.
Moshe Babaioff, Liad Blumrosen, Nicolas S. Lambert, Omer Reingold.
In proc. EC, pp. 221-222, 2011.
Improved Approximation Results for Stochastic Knapsack Problems.
Anand Bhalgat, Ashish Goel, Sanjeev Khanna.
In proc. SODA, pp. 1647-1665, 2011.
Address space randomization for mobile devices.
Hristo Bojinov, Dan Boneh, Rich Cannings, Iliyan Malchev.
In proc. WISEC, pp. 127-138, 2011.
Mobile token-based authentication on a budget.
Hristo Bojinov, Dan Boneh.
In proc. HotMobile, pp. 14-19, 2011.
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.
Homomorphic Signatures for Polynomial Functions.
Dan Boneh, David Mandell Freeman.
In proc. EUROCRYPT, pp. 149-168, 2011.
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.
Functional Encryption: Definitions and Challenges.
Dan Boneh, Amit Sahai, Brent Waters.
In proc. TCC, pp. 253-273, 2011.
Recent ideas for circumventing internet filtering.
Dan Boneh.
In XRDS, vol. 18, no. 2, pp. 36-40, 2011.
Efficient Selective Identity-Based Encryption Without Random Oracles.
Dan Boneh, Xavier Boyen.
In J. Cryptol., vol. 24, no. 4, pp. 659-693, 2011.
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.
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.
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.
Social Influence and Evolution of Market Share.
Simla Ceyhan, Mohammad Mousavi, Amin Saberi.
In Internet Math., vol. 7, no. 2, pp. 107-134, 2011.
Tight Hardness Results for Minimizing Discrepancy.
Moses Charikar, Alantha Newman, Aleksandar Nikolov.
In proc. SODA, pp. 1607-1614, 2011.
Improved Approximation Algorithms for Label Cover Problems.
Moses Charikar, MohammadTaghi Hajiaghayi, Howard J. Karloff.
In Algorithmica, vol. 61, no. 1, pp. 190-206, 2011.
Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding.
Chandra Chekuri, Jan Vondrák, Rico Zenklusen.
In proc. SODA, pp. 1080-1097, 2011.
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.
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.
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.
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.
Efficient k-nearest neighbor graph construction for generic similarity measures.
Wei Dong, Moses Charikar, Kai Li.
In proc. WWW, pp. 577-586, 2011.
Limitations of Randomized Mechanisms for Combinatorial Auctions.
Shaddin Dughmi, Jan Vondrák.
In proc. FOCS, pp. 502-511, 2011.
Euclidean Movement Minimization.
MohammadAmin Fazli, MohammadAli Safari, Nima Anari, Pooya Jalaly Khalilabadi, Mohammad Ghodsi.
In proc. CCCG, 2011.
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.
On Variants of the Matroid Secretary Problem.
Shayan Oveis Gharan, Jan Vondrák.
In proc. ESA, pp. 335-346, 2011.
A Randomized Rounding Approach to the Traveling Salesman Problem.
Shayan Oveis Gharan, Amin Saberi, Mohit Singh.
In proc. FOCS, pp. 550-559, 2011.
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus.
Shayan Oveis Gharan, Amin Saberi.
In proc. SODA, pp. 967-975, 2011.
Submodular Maximization by Simulated Annealing.
Shayan Oveis Gharan, Jan Vondrák.
In proc. SODA, pp. 1098-1116, 2011.
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.
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.
A renewable, modular, and time-responsive DNA circuit.
Ashish Goel, Morteza Ibrahimi.
In Nat. Comput., vol. 10, no. 1, pp. 467-485, 2011.
Pseudorandom generators for combinatorial shapes.
Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman.
In proc. STOC, pp. 253-262, 2011.
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.
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.
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.
Maximizing conjunctive views in deletion propagation.
Benny Kimelfeld, Jan Vondrák, Ryan Williams.
In proc. PODS, pp. 187-198, 2011.
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.
Memory-based embedded digital ATE.
Dongsoo Lee, Sang Phill Park, Ashish Goel, Kaushik Roy.
In proc. VTS, pp. 266-271, 2011.
Online Stochastic Matching: Online Actions Based on Offline Statistics.
Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi.
In proc. SODA, pp. 1285-1294, 2011.
Location Privacy via Private Proximity Testing.
Arvind Narayanan, Narendran Thiagarajan, Mugdha Lakhani, Michael Hamburg, Dan Boneh.
In proc. NDSS, 2011.
Best-Response Mechanisms.
Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar.
In proc. ICS, pp. 155-165, 2011.
Incentive-compatible distributed greedy protocols.
Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar.
In proc. PODC, pp. 335-336, 2011.
Best-response auctions.
Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar.
In proc. EC, pp. 351-360, 2011.
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.
Is Submodularity Testable?
C. Seshadhri, Jan Vondrák.
In proc. ICS, pp. 195-210, 2011.
The Power of Linear Estimators.
Gregory Valiant, Paul Valiant.
In proc. FOCS, pp. 403-412, 2011.
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.
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
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.
Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE.
Shweta Agrawal, Dan Boneh, Xavier Boyen.
In proc. CRYPTO, pp. 98-115, 2010.
Efficient Lattice (H)IBE in the Standard Model.
Shweta Agrawal, Dan Boneh, Xavier Boyen.
In proc. EUROCRYPT, pp. 553-572, 2010.
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.
Correlation Robust Stochastic Optimization.
Shipra Agrawal, Yichuan Ding, Amin Saberi, Yinyu Ye.
In proc. SODA, pp. 1087-1096, 2010.
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.
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.
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.
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.
Fast Incremental and Personalized PageRank.
Bahman Bahmani, Abdur Chowdhury, Ashish Goel.
In Proc. VLDB Endow., vol. 4, no. 3, pp. 173-184, 2010.
A Sequential Algorithm for Generating Random Graphs.
Mohsen Bayati, Jeong Han Kim, Amin Saberi.
In Algorithmica, vol. 58, no. 4, pp. 860-910, 2010.
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.
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.
Kamouflage: Loss-Resistant Password Management.
Hristo Bojinov, Elie Bursztein, Xavier Boyen, Dan Boneh.
In proc. ESORICS, pp. 286-302, 2010.
The emergence of cross channel scripting.
Hristo Bojinov, Elie Bursztein, Dan Boneh.
In Commun. ACM, vol. 53, no. 8, pp. 105-113, 2010.
Algebraic pseudorandom functions with improved efficiency from the augmented cascade.
Dan Boneh, Hart William Montgomery, Ananth Raghunathan.
In proc. ACM Conference on Computer and Communications Security, pp. 131-140, 2010.
Robust fingerprinting codes: a near optimal construction.
Dan Boneh, Aggelos Kiayias, Hart William Montgomery.
In proc. Digital Rights Management Workshop, pp. 3-12, 2010.
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.
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.
Vertex Sparsifiers and Abstract Rounding Algorithms.
Moses Charikar, Tom Leighton, Shi Li, Ankur Moitra.
In proc. FOCS, pp. 265-274, 2010.
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.
Local Global Tradeoffs in Metric Embeddings.
Moses Charikar, Konstantin Makarychev, Yury Makarychev.
In SIAM J. Comput., vol. 39, no. 6, pp. 2487-2512, 2010.
Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures.
Chandra Chekuri, Jan Vondrák, Rico Zenklusen.
In proc. FOCS, pp. 575-584, 2010.
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.
Pricing for Fairness: Distributed Resource Allocation for Multiple Objectives.
Sung-woo Cho, Ashish Goel.
In Algorithmica, vol. 57, no. 4, pp. 873-892, 2010.
Liquidity in Credit Networks: A Little Trust Goes a Long Way.
Pranav Dandekar, Ashish Goel, Ramesh Govindan, Ian Post.
In proc. NetEcon, 2010.
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.
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. Computational Complexity Conference, pp. 211-222, 2010.
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.
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.
The Submodular Welfare Problem with Demand Queries.
Uriel Feige, Jan Vondrák.
In Theory Comput., vol. 6, no. 1, pp. 247-290, 2010.
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.
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.
Small subset queries and bloom filters using ternary associative memories, with applications.
Ashish Goel, Pankaj Gupta.
In proc. SIGMETRICS, pp. 143-154, 2010.
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.
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.
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.
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.
Partial exposure in large games.
Ronen Gradwohl, Omer Reingold.
In Games Econ. Behav., vol. 68, no. 2, pp. 602-613, 2010.
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.
Efficiency improvements in constructing pseudorandom generators from one-way functions.
Iftach Haitner, Omer Reingold, Salil P. Vadhan.
In proc. STOC, pp. 437-446, 2010.
Efficiently learning mixtures of two Gaussians.
Adam Tauman Kalai, Ankur Moitra, Gregory Valiant.
In proc. STOC, pp. 553-562, 2010.
Subgraph sparsification and nearly optimal ultrasparsifiers.
Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng.
In proc. STOC, pp. 57-66, 2010.
Matroid matching: the power of local search.
Jon Lee, Maxim Sviridenko, Jan Vondrák.
In proc. STOC, pp. 369-378, 2010.
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.
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.
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.
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.
Settling the Polynomial Learnability of Mixtures of Gaussians.
Ankur Moitra, Gregory Valiant.
In proc. FOCS, pp. 93-102, 2010.
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.
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.
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.
A New Look at Selfish Routing.
Christos H. Papadimitriou, Gregory Valiant.
In proc. ICS, pp. 178-187, 2010.
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.
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.
Foreword.
Friedrich C. Simmel, Ashish Goel.
In Nat. Comput., vol. 9, no. 1, pp. 95-96, 2010.
A randomized embedding algorithm for trees.
Benny Sudakov, Jan Vondrák.
In Comb., vol. 30, no. 4, pp. 445-470, 2010.
Adnostic: Privacy Preserving Targeted Advertising.
Vincent Toubiana, Arvind Narayanan, Dan Boneh, Helen Nissenbaum, Solon Barocas.
In proc. NDSS, 2010.
Braess's Paradox in large random graphs.
Gregory Valiant, Tim Roughgarden.
In Random Struct. Algorithms, vol. 37, no. 4, pp. 495-515, 2010.