Publications of the Stanford Theory Group

2017
An
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi.
In Operations Research, 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.
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. Information Theory, vol. 63, no. 6, pp. 3368-3385, 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.
Constraining Pseudorandom Functions Privately.
Dan Boneh, Kevin Lewi, David J. Wu.
In proc. PKC (2), pp. 494-524, 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.
"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.
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.
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.
Approximately Efficient Two-Sided Combinatorial Auctions.
Riccardo Colini-Baldeschi, Paul W. Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, Stefano Turchetta.
In proc. EC, pp. 591-608, 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.
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.
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.
Deferred-Acceptance Auctions for Multiple Levels of Service.
Vasilis Gkatzelis, Evangelos Markakis, Tim Roughgarden.
In proc. EC, pp. 21-38, 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.
A PAC Approach to Application-Specific Algorithm Selection.
Rishi Gupta, Tim Roughgarden.
In SIAM J. Comput., vol. 46, no. 3, pp. 992-1017, 2017.
Repairing Reed-Solomon Codes.
Venkatesan Guruswami, Mary Wootters.
In IEEE Trans. Information Theory, vol. 63, no. 9, pp. 5684-5698, 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.
Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond.
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li.
In PVLDB, vol. 10, no. 12, pp. 2021-2024, 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.
Why prices need algorithms (invited talk).
Tim Roughgarden, Inbal Talgam-Cohen.
In proc. STOC, pp. 2, 2017.
The Price of Anarchy in Auctions.
Tim Roughgarden, Vasilis Syrgkanis, Éva Tardos.
In J. Artif. Intell. Res., vol. 59, pp. 59-101, 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.
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.
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.
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
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.
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 Security & Privacy, vol. 14, no. 6, pp. 7-9, 2016.
On Approximating Target Set Selection.
Moses Charikar, Yonatan Naamad, Anthony Wirth.
In proc. APPROX-RANDOM, pp. 4:1-4:16, 2016.
Mathematical foundations for social computing.
Yiling Chen, Arpita Ghosh, Michael Kearns, Tim Roughgarden, Jennifer Wortman Vaughan.
In Commun. ACM, vol. 59, no. 12, pp. 102-108, 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.
Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding.
Shaddin Dughmi, Tim Roughgarden, Qiqi Yan.
In J. ACM, vol. 63, no. 4, pp. 30:1-30:33, 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.
The price of anarchy in large games.
Michal Feldman, Nicole Immorlica, Brendan Lucier, Tim Roughgarden, Vasilis Syrgkanis.
In proc. STOC, pp. 963-976, 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 Computing, vol. 20, no. 1, pp. 8-10, 2016.
Optimal Cost-Sharing in General Resource Selection Games.
Vasilis Gkatzelis, Konstantinos Kollias, Tim Roughgarden.
In Operations Research, vol. 64, no. 6, pp. 1230-1238, 2016.
Network Formation of Coalition Loyalty Programs.
Arpit Goel, Vijay Kamble, Siddhartha Banerjee, Ashish Goel.
In SIGMETRICS Performance Evaluation Review, 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.
A PAC Approach to Application-Specific Algorithm Selection.
Rishi Gupta, Tim Roughgarden.
In proc. ITCS, pp. 123-134, 2016.
Decompositions of Triangle-Dense Graphs.
Rishi Gupta, Tim Roughgarden, C. Seshadhri.
In SIAM J. Comput., vol. 45, no. 2, pp. 197-215, 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.
Private Matchings and Allocations.
Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu.
In SIAM J. Comput., vol. 45, no. 6, pp. 1953-1984, 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 Security & Privacy, 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 of Computing, vol. 12, no. 1, pp. 1-3, 2016.
Learning Simple Auctions.
Jamie Morgenstern, Tim Roughgarden.
In proc. COLT, pp. 1298-1318, 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.
The Complexity of the k-means Method.
Tim Roughgarden, Joshua R. Wang.
In proc. ESA, pp. 78:1-78:14, 2016.
On the Communication Complexity of Approximate Fixed Points.
Tim Roughgarden, Omri Weinstein.
In proc. FOCS, pp. 229-238, 2016.
Why Prices Need Algorithms.
Tim Roughgarden, Inbal Talgam-Cohen.
In proc. IJCAI, pp. 4210-4212, 2016.
Intrinsic Robustness of the Price of Anarchy: Abstract of the Kalai Prize Talk.
Tim Roughgarden.
In proc. EC, pp. 457, 2016.
Ironing in the Dark.
Tim Roughgarden, Okke Schrijvers.
In proc. EC, pp. 1-18, 2016.
Minimizing Regret with Multiple Reserves.
Tim Roughgarden, Joshua R. Wang.
In proc. EC, pp. 601-616, 2016.
Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation).
Tim Roughgarden, Sergei Vassilvitskii, Joshua R. Wang.
In proc. SPAA, pp. 1-12, 2016.
Communication Complexity (for Algorithm Designers).
Tim Roughgarden.
In Foundations and Trends in Theoretical Computer Science, vol. 11, no. 3-4, pp. 217-404, 2016.
Network Cost-Sharing without Anonymity.
Tim Roughgarden, Okke Schrijvers.
In ACM Trans. Economics and Comput., vol. 4, no. 2, pp. 8:1-8:24, 2016.
Optimal and Robust Mechanism Design with Interdependent Values.
Tim Roughgarden, Inbal Talgam-Cohen.
In ACM Trans. Economics and Comput., vol. 4, no. 3, pp. 18:1-18:34, 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. Cryptology, 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.
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.
Preventing Unraveling in Social Networks: The Anchored k-Core Problem.
Kshipra Bhawalkar, Jon M. Kleinberg, Kevin Lewi, Tim Roughgarden, Aneesh Sharma.
In SIAM J. Discrete Math., vol. 29, no. 3, pp. 1452-1475, 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.
Introduction to the Special Issue - Algorithmic Game Theory - STOC/FOCS/SODA 2011.
Shuchi Chawla, Lisa Fleischer, Jason D. Hartline, Tim Roughgarden.
In Games and Economic Behavior, vol. 92, pp. 228-231, 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.
Special Section of Games and Economic Behavior dedicated to the 11th and 12th ACM Conference on Electronic Commerce.
Yan Chen, Tim Roughgarden.
In Games and Economic Behavior, vol. 91, pp. 283, 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.
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.
Revenue maximization with a single sample.
Peerapong Dhangwatnotai, Tim Roughgarden, Qiqi Yan.
In Games and Economic Behavior, vol. 91, pp. 318-333, 2015.
Limitations of randomized mechanisms for combinatorial auctions.
Shaddin Dughmi, Jan Vondrák.
In Games and Economic Behavior, 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 Kakade, Aaron Sidford.
In proc. ICML, pp. 2540-2548, 2015.
How Hard is Inference for Structured Prediction?
Amir Globerson, Tim Roughgarden, David Sontag, Cafer Yildirim.
In proc. ICML, pp. 2181-2190, 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.
Public Projects, Boolean Functions, and the Borders of Border's Theorem.
Parikshit Gopalan, Noam Nisan, Tim Roughgarden.
In proc. EC, pp. 395, 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.
Making the Most of Your Samples.
Zhiyi Huang, Yishay Mansour, Tim Roughgarden.
In proc. EC, pp. 45-60, 2015.
Restoring Pure Equilibria to Weighted Congestion Games.
Konstantinos Kollias, Tim Roughgarden.
In ACM Trans. Economics and Comput., vol. 3, no. 4, pp. 21:1-21:24, 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.
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.
On the Pseudo-Dimension of Nearly Optimal Auctions.
Jamie Morgenstern, Tim Roughgarden.
In proc. NIPS, pp. 136-144, 2015.
Why Prices Need Algorithms.
Tim Roughgarden, Inbal Talgam-Cohen.
In proc. EC, pp. 19-36, 2015.
Intrinsic Robustness of the Price of Anarchy.
Tim Roughgarden.
In J. ACM, vol. 62, no. 5, pp. 32:1-32:42, 2015.
Local smoothness and the price of anarchy in splittable congestion games.
Tim Roughgarden, Florian Schoppmann.
In J. Economic Theory, vol. 156, pp. 317-342, 2015.
Special Section on the Fifty-Third IEEE Annual Symposium on Foundations of Computer Science (FOCS 2012).
Tim Roughgarden.
In SIAM J. Comput., vol. 44, no. 5, pp. 1286, 2015.
Why prices need algorithms.
Tim Roughgarden, Inbal Talgam-Cohen.
In SIGecom Exchanges, vol. 14, no. 2, pp. 35-40, 2015.
The Price of Anarchy in Games of Incomplete Information.
Tim Roughgarden.
In ACM Trans. Economics and Comput., vol. 3, no. 1, pp. 6:1-6:20, 2015.
It'll Probably Work Out: Improved List-Decoding Through Random Operations.
Atri Rudra, Mary Wootters.
In proc. ITCS, pp. 287-296, 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
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.
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.
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.
Weighted Congestion Games: The Price of Anarchy, Universal Worst-Case Examples, and Tightness.
Kshipra Bhawalkar, Martin Gairing, Tim Roughgarden.
In ACM Trans. Economics and Comput., vol. 2, no. 4, pp. 14:1-14:23, 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.
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.
The sample complexity of revenue maximization.
Richard Cole, Tim Roughgarden.
In proc. STOC, pp. 243-252, 2014.
Black-Box Randomized Reductions in Algorithmic Mechanism Design.
Shaddin Dughmi, Tim Roughgarden.
In SIAM J. Comput., vol. 43, no. 1, pp. 312-336, 2014.
The performance of deferred-acceptance auctions.
Paul Dütting, Vasilis Gkatzelis, Tim Roughgarden.
In proc. EC, pp. 187-204, 2014.
Modularity and greed in double auctions.
Paul Dütting, Tim Roughgarden, Inbal Talgam-Cohen.
In proc. EC, pp. 241-258, 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.
Optimal Cost-Sharing in Weighted Congestion Games.
Vasilis Gkatzelis, Konstantinos Kollias, Tim Roughgarden.
In proc. WINE, pp. 72-88, 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 Wireless Personal Communications, vol. 74, no. 2, pp. 285-305, 2014.
Fault tolerance in large games.
Ronen Gradwohl, Omer Reingold.
In Games and Economic Behavior, vol. 86, pp. 438-457, 2014.
Decompositions of triangle-dense graphs.
Rishi Gupta, Tim Roughgarden, C. Seshadhri.
In proc. ITCS, pp. 471-482, 2014.
A New Interactive Hashing Theorem.
Iftach Haitner, Omer Reingold.
In J. Cryptology, 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.
Privately Solving Linear Programs.
Justin Hsu, Aaron Roth, Tim Roughgarden, Jonathan Ullman.
In proc. ICALP (1), pp. 612-624, 2014.
Private matchings and allocations.
Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu.
In proc. STOC, pp. 21-30, 2014.
An Experimental Study of TLS Forward Secrecy Deployments.
Lin-Shung Huang, Shrikant Adhikarla, Dan Boneh, Collin Jackson.
In IEEE Internet Computing, 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.
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.
Generalized Efficiency Bounds in Distributed Resource Allocation.
Jason R. Marden, Tim Roughgarden.
In IEEE Trans. Automat. Contr., vol. 59, no. 3, pp. 571-584, 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.
Pseudorandom Graphs in Data Structures.
Omer Reingold, Ron D. Rothblum, Udi Wieder.
In proc. ICALP (1), pp. 943-954, 2014.
Barriers to Near-Optimal Equilibria.
Tim Roughgarden.
In proc. FOCS, pp. 71-80, 2014.
Network Cost-Sharing without Anonymity.
Tim Roughgarden, Okke Schrijvers.
In proc. SAGT, pp. 134-145, 2014.
Approximately optimal mechanism design: motivation, examples, and lessons learned.
Tim Roughgarden.
In SIGecom Exchanges, vol. 13, no. 2, pp. 4-20, 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.
Message-Passing Algorithms for Sparse Network Alignment.
Mohsen Bayati, David F. Gleich, Amin Saberi, Ying Wang.
In TKDD, vol. 7, no. 1, pp. 3:1-3:31, 2013.
Near-optimal multi-unit auctions with ordered bidders.
Sayan Bhattacharya, Elias Koutsoupias, Janardhan Kulkarni, Stefano Leonardi, Tim Roughgarden, Xiaoming Xu.
In proc. EC, pp. 91-102, 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.
Testing
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 Exchanges, 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 Digital Signal Processing, 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 Wireless Personal Communications, vol. 71, no. 4, pp. 2605-2623, 2013.
DNF sparsification and a faster deterministic counting algorithm.
Parikshit Gopalan, Raghu Meka, Omer Reingold.
In Computational Complexity, 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 PVLDB, 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 Operations Research, 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.
Pseudorandomness for Regular Branching Programs via Fourier Analysis.
Omer Reingold, Thomas Steinke, Salil P. Vadhan.
In proc. APPROX-RANDOM, pp. 655-670, 2013.
Marginals-to-Models Reducibility.
Tim Roughgarden, Michael Kearns.
In proc. NIPS, pp. 1043-1051, 2013.
Optimal and near-optimal mechanism design with interdependent values.
Tim Roughgarden, Inbal Talgam-Cohen.
In proc. EC, pp. 767-784, 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 Journal of Machine Learning Research, vol. 14, no. 1, pp. 1605-1626, 2013.
2012
Combinatorial auctions with restricted complements.
Ittai Abraham, Moshe Babaioff, Shaddin Dughmi, Tim Roughgarden.
In proc. EC, pp. 3-16, 2012.
Price of Correlations in Stochastic Optimization.
Shipra Agrawal, Yichuan Ding, Amin Saberi, Yinyu Ye.
In Operations Research, 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.
Sketching valuation functions.
Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, Tim Roughgarden.
In proc. SODA, pp. 1025-1035, 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
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou.
In proc. SODA, pp. 388-405, 2012.
Preventing Unraveling in Social Networks: The Anchored k-Core Problem.
Kshipra Bhawalkar, Jon M. Kleinberg, Kevin Lewi, Tim Roughgarden, Aneesh Sharma.
In proc. ICALP (2), pp. 440-451, 2012.
Simultaneous Single-Item Auctions.
Kshipra Bhawalkar, Tim Roughgarden.
In proc. WINE, pp. 337-349, 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.
Bottleneck links, variable demand, and the tragedy of the commons.
Richard Cole, Yevgeniy Dodis, Tim Roughgarden.
In Networks, vol. 60, no. 3, pp. 194-203, 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 Operations Research, 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.
Revenue Submodularity.
Shaddin Dughmi, Tim Roughgarden, Mukund Sundararajan.
In Theory of Computing, vol. 8, no. 1, pp. 95-119, 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.
Universally Utility-maximizing Privacy Mechanisms.
Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan.
In SIAM J. Comput., vol. 41, no. 6, pp. 1673-1693, 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 of Computing, vol. 8, no. 1, pp. 351-368, 2012.
DNF Sparsification and a Faster Deterministic Counting Algorithm.
Parikshit Gopalan, Raghu Meka, Omer Reingold.
In proc. IEEE Conference on Computational Complexity, 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 Proceedings of the IEEE, vol. 100, no. Centennial-Issue, pp. 1659-1673, 2012.
Prior-free auctions with ordered bidders.
Stefano Leonardi, Tim Roughgarden.
In proc. STOC, pp. 427-434, 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.
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.
The price of anarchy in games of incomplete information.
Tim Roughgarden.
In proc. EC, pp. 862-879, 2012.
Supply-limiting mechanisms.
Tim Roughgarden, Inbal Talgam-Cohen, Qiqi Yan.
In proc. EC, pp. 844-861, 2012.
Intrinsic robustness of the price of anarchy.
Tim Roughgarden.
In Commun. ACM, vol. 55, no. 7, pp. 116-123, 2012.
The price of anarchy in games of incomplete information.
Tim Roughgarden.
In SIGecom Exchanges, vol. 11, no. 1, pp. 18-20, 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.
Welfare Guarantees for Combinatorial Auctions with Item Bidding.
Kshipra Bhawalkar, Tim Roughgarden.
In proc. SODA, pp. 700-709, 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 ACM Crossroads, vol. 18, no. 2, pp. 36-40, 2011.
Efficient Selective Identity-Based Encryption Without Random Oracles.
Dan Boneh, Xavier Boyen.
In J. Cryptology, 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 Mathematics, 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.
Truthful Approximation Schemes for Single-Parameter Agents.
Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden.
In SIAM J. Comput., vol. 40, no. 3, pp. 915-933, 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.
From convex optimization to randomized mechanisms: toward optimal combinatorial auctions.
Shaddin Dughmi, Tim Roughgarden, Qiqi Yan.
In proc. STOC, pp. 149-158, 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.
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 Natural Computing, 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.
Restoring Pure Equilibria to Weighted Congestion Games.
Konstantinos Kollias, Tim Roughgarden.
In proc. ICALP (2), pp. 539-551, 2011.
Metric Clustering via Consistent Labeling.
Robert Krauthgamer, Tim Roughgarden.
In Theory of Computing, vol. 7, no. 1, pp. 49-74, 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. VLSI Syst., vol. 19, no. 9, pp. 1727-1730, 2011.
Flexible Tree Matching.
Ranjitha Kumar, Jerry O. Talton, Salman Ahmad, Tim Roughgarden, Scott R. Klemmer.
In proc. IJCAI, pp. 2674-2679, 2011.
Memory-based embedded digital ATE.
Dongsoo Lee, Sang Phill Park, Ashish Goel, Kaushik Roy.
In proc. VTS, pp. 266-271, 2011.
Stronger Bounds on Braess's Paradox and the Maximum Latency of Selfish Routing.
Henry C. Lin, Tim Roughgarden, Éva Tardos, Asher Walkover.
In SIAM J. Discrete Math., vol. 25, no. 4, pp. 1667-1686, 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.
Uncoupled potentials for proportional allocation markets.
Uri Nadav, Ramesh Johari, Tim Roughgarden.
In proc. CDC-ECE, pp. 4479-4484, 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 Exchanges, vol. 10, no. 2, pp. 16-18, 2011.
Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games.
Tim Roughgarden, Florian Schoppmann.
In proc. SODA, pp. 255-267, 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.
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 Autonomous Agents and Multi-Agent Systems, vol. 20, no. 2, pp. 105-122, 2010.
Fast Incremental and Personalized PageRank.
Bahman Bahmani, Abdur Chowdhury, Ashish Goel.
In PVLDB, 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
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan.
In proc. STOC, pp. 201-210, 2010.
Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness.
Kshipra Bhawalkar, Martin Gairing, Tim Roughgarden.
In proc. ESA (2), pp. 17-28, 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.
None
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.
Revenue maximization with a single sample.
Peerapong Dhangwatnotai, Tim Roughgarden, Qiqi Yan.
In proc. EC, pp. 129-138, 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.
Truthfulness via smoothed complexity.
Shaddin Dughmi, Tim Roughgarden.
In proc. BQGT, pp. 21:1, 2010.
Black-Box Randomized Reductions in Algorithmic Mechanism Design.
Shaddin Dughmi, Tim Roughgarden.
In proc. FOCS, pp. 775-784, 2010.
The Submodular Welfare Problem with Demand Queries.
Uriel Feige, Jan Vondrák.
In Theory of Computing, 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(
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 and Economic Behavior, 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. VLSI Syst., vol. 18, no. 12, pp. 1710-1723, 2010.
Generalized efficiency bounds in distributed resource allocation.
Jason R. Marden, Tim Roughgarden.
In proc. CDC, pp. 2233-2238, 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.
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.
Fully Distributed Algorithms for Convex Optimization Problems.
Damon Mosk-Aoyama, Tim Roughgarden, Devavrat Shah.
In SIAM Journal on Optimization, vol. 20, no. 6, pp. 3260-3279, 2010.
The Limits of Smoothness: A Primal-Dual Framework for Price of Anarchy Bounds.
Uri Nadav, Tim Roughgarden.
In proc. WINE, pp. 319-326, 2010.
A Scalable Circuit-Architecture Co-Design to Improve Memory Yield for High-Performance Processors.
Patrick Ndai, Ashish Goel, Kaushik Roy.
In IEEE Trans. VLSI 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.
Interactive privacy via the median mechanism.
Aaron Roth, Tim Roughgarden.
In proc. STOC, pp. 765-774, 2010.
Algorithmic game theory.
Tim Roughgarden.
In Commun. ACM, vol. 53, no. 7, pp. 78-86, 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 Natural Computing, vol. 9, no. 1, pp. 95-96, 2010.
A randomized embedding algorithm for trees.
Benny Sudakov, Jan Vondrák.
In Combinatorica, 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.