# Kunal Talwar

According to our database

Collaborative distances:

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

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2020

Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses.

CoRR, 2020

Exploring the Memorization-Generalization Continuum in Deep Learning.

CoRR, 2020

Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation.

CoRR, 2020

Private stochastic convex optimization: optimal rates in linear time.

Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs.

SIAM J. Comput., 2019

Rényi Differential Privacy of the Sampled Gaussian Mechanism.

CoRR, 2019

Private selection from private candidates.

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

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

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

Computational Separations between Sampling and Optimization.

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Private Stochastic Convex Optimization with Optimal Rates.

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Semi-Cyclic Stochastic Gradient Descent.

Proceedings of the 36th International Conference on Machine Learning, 2019

Better Algorithms for Stochastic Bandits with Adversarial Corruptions.

Proceedings of the Conference on Learning Theory, 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

Scalable Private Learning with PATE.

Proceedings of the 6th International Conference on Learning Representations, 2018

Learning Differentially Private Recurrent Language Models.

Proceedings of the 6th International Conference on Learning Representations, 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

Learning Differentially Private Language Models Without Losing Accuracy.

CoRR, 2017

Oblivious Stash Shuffle.

CoRR, 2017

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

CoRR, 2017

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

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

Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data.

Proceedings of the 5th International Conference on Learning Representations, 2017

Short and Deep: Sketching and Neural Networks.

Proceedings of the 5th International Conference on Learning Representations, 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

Sketching and Neural Networks.

CoRR, 2016

TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems.

CoRR, 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

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations.

Discret. Comput. Geom., 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

Vertex Sparsifiers: New Results from Old Techniques.

SIAM J. Comput., 2014

Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry.

CoRR, 2014

Factorization Norms and Hereditary Discrepancy.

CoRR, 2014

Consistent Weighted Sampling Made Fast, Small, and Easy.

CoRR, 2014

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

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

Random Rates for 0-Extension and Low-Diameter Decompositions.

CoRR, 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

Efficient distributed approximation algorithms via probabilistic tree embeddings.

Distributed Comput., 2012

Unconditional differentially private mechanisms for linear queries.

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

2011

The Limits of Two-Party Differential Privacy.

Electronic Colloquium on Computational Complexity (ECCC), 2011

Making Doubling Metrics Geodesic.

Algorithmica, 2011

2010

Ultra-low-dimensional embeddings for doubling metrics.

J. ACM, 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

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

Improving Integrality Gaps via Chvátal-Gomory Rounding.

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

Differentially Private Approximation Algorithms

CoRR, 2009

Approximating the Bandwidth of Caterpillars.

Algorithmica, 2009

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

Algorithmica, 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 Edition, 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

A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property.

Theor. Comput. Sci., 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

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

2004

Approximating metrics by tree metrics.

SIGACT News, 2004

A tight bound on approximating arbitrary metrics by tree metrics.

J. Comput. Syst. Sci., 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

An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents.

Internet Math., 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 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