# Kunal Talwar

According to our database

Collaborative distances:

^{1}, Kunal Talwar authored at least 82 papers between 2001 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity.

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

Adversarially Robust Generalization Requires More Data.

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Online Linear Quadratic Control.

Proceedings of the 35th International Conference on Machine Learning, 2018

Privacy Amplification by Iteration.

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Balancing Vectors in Any Norm.

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Online learning over a finite action set with limited switching.

Proceedings of the Conference On Learning Theory, 2018

2017

LAST but not Least: Online Spanners for Buy-at-Bulk.

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On the Protection of Private Information in Machine Learning Systems: Two Recent Approches.

Proceedings of the 30th IEEE Computer Security Foundations Symposium, 2017

2016

Approximating Metric Spaces by Tree Metrics.

Encyclopedia of Algorithms, 2016

The Geometry of Differential Privacy: The Small Database and Approximate Cases.

SIAM J. Comput., 2016

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions.

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Deep Learning with Differential Privacy.

Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016

2015

Graphical balanced allocations and the (1 + β)-choice process.

Random Struct. Algorithms, 2015

Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations.

Discrete & Computational Geometry, 2015

Approximating Hereditary Discrepancy via Small Width Ellipsoids.

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Nearly Optimal Private LASSO.

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Navigation made personal: inferring driving preferences from GPS traces.

Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2015

2014

Analyze gauss: optimal bounds for privacy-preserving principal component analysis.

Proceedings of the Symposium on Theory of Computing, 2014

Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs.

Proceedings of the Symposium on Theory of Computing, 2014

Non-Uniform Graph Partitioning.

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Balanced Allocations: A Simple Proof for the Heavily Loaded Case.

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Changing Bases: Multistage Optimization for Matroids and Matchings.

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Using Convex Relaxations for Efficiently and Privately Releasing Marginals.

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier.

Proceedings of the Approximation, 2014

Approximation Algorithms.

Proceedings of the Tractability: Practical Approaches to Hard Problems, 2014

2013

The geometry of differential privacy: the sparse and approximate cases.

Proceedings of the Symposium on Theory of Computing Conference, 2013

Sparsest cut on bounded treewidth graphs: algorithms and hardness results.

Proceedings of the Symposium on Theory of Computing Conference, 2013

On differentially private low rank approximation.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Minimum Makespan Scheduling with Low Rank Processing Times.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Unconditional differentially private mechanisms for linear queries.

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Making Doubling Metrics Geodesic.

Algorithmica, 2011

2010

Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs.

Combinatorica, 2010

Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms.

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010

On the geometry of differential privacy.

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

The (1 + beta)-Choice Process and Weighted Balls-into-Bins.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Differentially Private Combinatorial Optimization.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Hard Instances for Satisfiability and Quasi-one-way Functions.

Proceedings of the Innovations in Computer Science, 2010

Lower Bounds on Near Neighbor Search via Metric Expansion.

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

The Limits of Two-Party Differential Privacy.

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Improving Integrality Gaps via Chvátal-Gomory Rounding.

Proceedings of the Approximation, 2010

Vertex Sparsifiers: New Results from Old Techniques.

Proceedings of the Approximation, 2010

2009

A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids.

Theor. Comput. Sci., 2009

Virtual Ring Routing Trends.

Proceedings of the Distributed Computing, 23rd International Symposium, 2009

Quincy: fair scheduling for distributed computing clusters.

Proceedings of the 22nd ACM Symposium on Operating Systems Principles 2009, 2009

Secretary problems: weights and discounts.

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Differentially Private Combinatorial Optimization.

Proceedings of the Parameterized complexity and approximation algorithms, 13.12., 2009

2008

Approximating Metric Spaces by Tree Metrics.

Proceedings of the Encyclopedia of Algorithms, 2008

Ultra-low-dimensional embeddings for doubling metrics.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Efficient distributed approximation algorithms via probabilistic tree embeddings.

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

How to Complete a Doubling Metric.

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem.

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.

Electronic Colloquium on Computational Complexity (ECCC), 2007

Balanced allocations: the weighted case.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

The price of privacy and the limits of LP decoding.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Hardness of routing with congestion in directed graphs.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Privacy, accuracy, and consistency too: a holistic solution to contingency table release.

Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

Reconstructing approximate tree metrics.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

Mechanism Design via Differential Privacy.

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Balloon Popping With Applications to Ascending Auctions.

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Hardness of Low Congestion Routing in Directed Graphs.

Electronic Colloquium on Computational Complexity (ECCC), 2006

Approximating unique games.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

A Push-Relabel Algorithm for Approximating Degree Bounded MSTs.

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

A Simple Characterization for Truth-Revealing Single-Item Auctions.

Proceedings of the Internet and Network Economics, First International Workshop, 2005

Click Fraud Resistant Methods for Learning Click-Through Rates.

Proceedings of the Internet and Network Economics, First International Workshop, 2005

A Primal-Dual Algorithm for Computing Fisher Equilibrium in the Absence of Gross Substitutability Property.

Proceedings of the Internet and Network Economics, First International Workshop, 2005

On Privacy-Preserving Histograms.

Proceedings of the UAI '05, 2005

The Generalized Deadlock Resolution Problem.

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Approximating the Bandwidth of Caterpillars.

Proceedings of the Approximation, 2005

What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs.

Proceedings of the Approximation, 2005

2004

Approximating metrics by tree metrics.

SIGACT News, 2004

Bypassing the embedding: algorithms for low dimensional metrics.

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The complexity of pure Nash equilibria.

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Approximate classification via earthmover metrics.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

A tight bound on approximating arbitrary metrics by tree metrics.

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

The Price of Truth: Frugality in Truthful Mechanisms.

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

An improved approximation algorithm for the 0-extension problem.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

An approximate truthful mechanism for combinatorial auctions with single parameter agents.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor.

Proceedings of the Approximation, 2003

Paths, Trees, and Minimum Latency Tours.

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

The Single-Sink Buy-at-Bulk LP Has Constant Integrality Gap.

Proceedings of the Integer Programming and Combinatorial Optimization, 2002

2001

Detecting Format String Vulnerabilities with Type Qualifiers.

Proceedings of the 10th USENIX Security Symposium, 2001