Kunal Talwar

According to our database, Kunal Talwar authored at least 133 papers between 2001 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

PINE: Efficient Norm-Bound Verification for Secret-Shared Vectors.

Guy N. Rothblum, Eran Omri, Junye Chen, Kunal Talwar

CoRR, 2023

Federated Learning with Differential Privacy for End-to-End Speech Recognition.

Martin Pelikan, Sheikh Shams Azam, Vitaly Feldman, Jan Honza Silovsky, Kunal Talwar, Tatiana Likhomanenko

CoRR, 2023

Samplable Anonymous Aggregation for Private Federated Data Analysis.

Kunal Talwar, Shan Wang, Audra McMillan, Vojta Jina, Vitaly Feldman, Bailey Basile, Áine Cahill, Yi Sheng Chan, Mike Chatzidakis, Junye Chen, Oliver Chick, Mona Chitnis, Suman Ganta, Yusuf Goren, Filip Granqvist, Kristine Guo, Frederic Jacobs, Omid Javidbakht, Albert Liu, Richard Low, Dan Mascenik, Steve Myers, David Park, Wonhee Park, Gianni Parsa, Tommy Pauly, Christian Priebe, Rehan Rishi, Guy N. Rothblum, Michael Scaria, Linmao Song, Congzheng Song, Karl Tarbe, Sebastian Vogt, Luke Winstrom, Shundong Zhou

CoRR, 2023

Differentially Private Heavy Hitter Detection using Federated Analytics.

Karan N. Chadha, Junye Chen, John C. Duchi, Vitaly Feldman, Hanieh Hashemi, Omid Javidbakht, Audra McMillan, Kunal Talwar

CoRR, 2023

Stronger Privacy Amplification by Shuffling for Renyi and Approximate Differential Privacy.

Vitaly Feldman, Audra McMillan, Kunal Talwar

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fast Optimal Locally Private Mean Estimation via Random Projections.

Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime.

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

Proceedings of the International Conference on Machine Learning, 2023

Private Online Prediction from Experts: Separations and Faster Rates.

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling.

Jason M. Altschuler, Kunal Talwar

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Concentration of the Langevin Algorithm's Stationary Distribution.

Jason M. Altschuler, Kunal Talwar

CoRR, 2022

Private Federated Statistics in an Interactive Setting.

Audra McMillan, Omid Javidbakht, Kunal Talwar, Elliot Briggs, Mike Chatzidakis, Junye Chen, John C. Duchi, Vitaly Feldman, Yusuf Goren, Michael Hesse, Vojta Jina, Anil Katti, Albert Liu, Cheney Lyford, Joey Meyer, Alex Palmer, David Park, Wonhee Park, Gianni Parsa, Paul Pelzl, Rehan Rishi, Congzheng Song, Shan Wang, Shundong Zhou

CoRR, 2022

FLAIR: Federated Learning Annotated Image Repository.

Congzheng Song, Filip Granqvist, Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Subspace Recovery from Heterogeneous Data with Non-isotropic Noise.

John C. Duchi, Vitaly Feldman, Lunjia Hu, Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Mean Estimation with User-level Privacy under Data Heterogeneity.

Rachel Cummings, Vitaly Feldman, Audra McMillan, Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss.

Jason M. Altschuler, Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Practical Almost-Linear-Time Approximation Algorithms for Hybrid and Overlapping Graph Clustering.

Lorenzo Orecchia, Konstantinos Ameranis, Charalampos E. Tsourakakis, Kunal Talwar

Proceedings of the International Conference on Machine Learning, 2022

Private frequency estimation via projective geometry.

Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar

Proceedings of the International Conference on Machine Learning, 2022

Optimal Algorithms for Mean Estimation under Local Differential Privacy.

Hilal Asi, Vitaly Feldman, Kunal Talwar

Proceedings of the International Conference on Machine Learning, 2022

Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation.

Kunal Talwar

Proceedings of the 3rd Symposium on Foundations of Responsible Computing, 2022

2021

Online Learning over a Finite Action Set with Limited Switching.

Jason M. Altschuler, Kunal Talwar

Math. Oper. Res., 2021

Private Stochastic Convex Optimization: Optimal Rates in 𝓁₁ Geometry.

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

CoRR, 2021

When is memorization of irrelevant training data necessary for high-accuracy learning?

Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Characterizing Structural Regularities of Labeled Data in Overparameterized Models.

Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, Michael C. Mozer

Proceedings of the 38th International Conference on Machine Learning, 2021

Lossless Compression of Efficient Private Local Randomizers.

Vitaly Feldman, Kunal Talwar

Proceedings of the 38th International Conference on Machine Learning, 2021

Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry.

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar

Proceedings of the 38th International Conference on Machine Learning, 2021

Private Adaptive Gradient Methods for Convex Optimization.

Hilal Asi, John C. Duchi, Alireza Fallah, Omid Javidbakht, Kunal Talwar

Proceedings of the 38th International Conference on Machine Learning, 2021

Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling.

Vitaly Feldman, Audra McMillan, Kunal Talwar

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Exploring the Memorization-Generalization Continuum in Deep Learning.

Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, Michael C. Mozer

CoRR, 2020

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

Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, Abhradeep Thakurta

CoRR, 2020

Private stochastic convex optimization: optimal rates in linear time.

Vitaly Feldman, Tomer Koren, Kunal Talwar

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

On the Error Resistance of Hinge-Loss Minimization.

Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC.

Arun Ganesh, Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses.

Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Stochastic Optimization with Laggard Data Pipelines.

Naman Agarwal, Rohan Anil, Tomer Koren, Kunal Talwar, Cyril Zhang

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019

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

Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar

SIAM J. Comput., 2019

Rényi Differential Privacy of the Sampled Gaussian Mechanism.

Ilya Mironov, Kunal Talwar, Li Zhang

CoRR, 2019

Private selection from private candidates.

Jingcheng Liu, Kunal Talwar

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

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

Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta

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

Computational Separations between Sampling and Optimization.

Kunal Talwar

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.

Raef Bassily, Vitaly Feldman, Kunal Talwar, Abhradeep Guha Thakurta

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

Semi-Cyclic Stochastic Gradient Descent.

Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, Kunal Talwar

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

Better Algorithms for Stochastic Bandits with Adversarial Corruptions.

Anupam Gupta, Tomer Koren, Kunal Talwar

Proceedings of the Conference on Learning Theory, 2019

2018

Adversarially Robust Generalization Requires More Data.

Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, Aleksander Madry

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

Online Linear Quadratic Control.

Alon Cohen, Avinatan Hassidim, Tomer Koren, Nevena Lazic, Yishay Mansour, Kunal Talwar

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

Scalable Private Learning with PATE.

Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Úlfar Erlingsson

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

Learning Differentially Private Recurrent Language Models.

H. Brendan McMahan, Daniel Ramage, Kunal Talwar, Li Zhang

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

Privacy Amplification by Iteration.

Vitaly Feldman, Ilya Mironov, Kunal Talwar, Abhradeep Thakurta

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

Balancing Vectors in Any Norm.

Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, Nicole Tomczak-Jaegermann

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

2017

Learning Differentially Private Language Models Without Losing Accuracy.

H. Brendan McMahan, Daniel Ramage, Kunal Talwar, Li Zhang

CoRR, 2017

Oblivious Stash Shuffle.

Petros Maniatis, Ilya Mironov, Kunal Talwar

CoRR, 2017

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

Martín Abadi, Úlfar Erlingsson, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Nicolas Papernot, Kunal Talwar, Li Zhang

CoRR, 2017

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

Anupam Gupta, R. Ravi, Kunal Talwar, Seeun William Umboh

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

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

Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, Ian J. Goodfellow, Kunal Talwar

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

Short and Deep: Sketching and Neural Networks.

Amit Daniely, Nevena Lazic, Yoram Singer, Kunal Talwar

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

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

Martín Abadi, Úlfar Erlingsson, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Nicolas Papernot, Kunal Talwar, Li Zhang

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

2016

Approximating Metric Spaces by Tree Metrics.

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar

Encyclopedia of Algorithms, 2016

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

Aleksandar Nikolov, Kunal Talwar, Li Zhang

SIAM J. Comput., 2016

Sketching and Neural Networks.

Amit Daniely, Nevena Lazic, Yoram Singer, Kunal Talwar

CoRR, 2016

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

Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Gregory S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian J. Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Józefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Gordon Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul A. Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda B. Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, Xiaoqiang Zheng

CoRR, 2016

Deep Learning with Differential Privacy.

Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, Li Zhang

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

2015

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

Yuval Peres, Kunal Talwar, Udi Wieder

Random Struct. Algorithms, 2015

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

Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson

Electron. Colloquium Comput. Complex., 2015

Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations.

Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar

Discret. Comput. Geom., 2015

Approximating Hereditary Discrepancy via Small Width Ellipsoids.

Aleksandar Nikolov, Kunal Talwar

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

Nearly Optimal Private LASSO.

Kunal Talwar, Abhradeep Thakurta, Li Zhang

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.

Daniel Delling, Andrew V. Goldberg, Moisés Goldszmidt, John Krumm, Kunal Talwar, Renato F. Werneck

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

2014

Vertex Sparsifiers: New Results from Old Techniques.

Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, Kunal Talwar

SIAM J. Comput., 2014

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

Kunal Talwar, Abhradeep Thakurta, Li Zhang

CoRR, 2014

Factorization Norms and Hereditary Discrepancy.

Jirí Matousek, Aleksandar Nikolov, Kunal Talwar

CoRR, 2014

Consistent Weighted Sampling Made Fast, Small, and Easy.

Bernhard Haeupler, Mark S. Manasse, Kunal Talwar

CoRR, 2014

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

Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, Li Zhang

Proceedings of the Symposium on Theory of Computing, 2014

Non-Uniform Graph Partitioning.

Robert Krauthgamer, Joseph Naor, Roy Schwartz, Kunal Talwar

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

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

Kunal Talwar, Udi Wieder

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

Changing Bases: Multistage Optimization for Matroids and Matchings.

Anupam Gupta, Kunal Talwar, Udi Wieder

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

Using Convex Relaxations for Efficiently and Privately Releasing Marginals.

Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar

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

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

Ittai Abraham, Shiri Chechik, Kunal Talwar

Proceedings of the Approximation, 2014

Approximation Algorithms.

Mohit Singh, Kunal Talwar

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

2013

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

Anupam Gupta, Kunal Talwar

CoRR, 2013

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

Aleksandar Nikolov, Kunal Talwar, Li Zhang

Proceedings of the Symposium on Theory of Computing Conference, 2013

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

Anupam Gupta, Kunal Talwar, David Witmer

Proceedings of the Symposium on Theory of Computing Conference, 2013

On differentially private low rank approximation.

Michael Kapralov, Kunal Talwar

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

Minimum Makespan Scheduling with Low Rank Processing Times.

Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, Udi Wieder

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

2012

Efficient distributed approximation algorithms via probabilistic tree embeddings.

Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, Kunal Talwar

Distributed Comput., 2012

Unconditional differentially private mechanisms for linear queries.

Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, Kunal Talwar

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

2011

The Limits of Two-Party Differential Privacy.

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2011

Making Doubling Metrics Geodesic.

Anupam Gupta, Kunal Talwar

Algorithmica, 2011

2010

Ultra-low-dimensional embeddings for doubling metrics.

T.-H. Hubert Chan, Anupam Gupta, Kunal Talwar

J. ACM, 2010

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

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

Comb., 2010

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

Anupam Gupta, Aaron Roth, Grant Schoenebeck, Kunal Talwar

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

On the geometry of differential privacy.

Moritz Hardt, Kunal Talwar

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

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

Yuval Peres, Kunal Talwar, Udi Wieder

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

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

Andrej Bogdanov, Kunal Talwar, Andrew Wan

Proceedings of the Innovations in Computer Science, 2010

Lower Bounds on Near Neighbor Search via Metric Expansion.

Rina Panigrahy, Kunal Talwar, Udi Wieder

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

Improving Integrality Gaps via Chvátal-Gomory Rounding.

Mohit Singh, Kunal Talwar

Proceedings of the Approximation, 2010

2009

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

Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, Kunal Talwar

Theor. Comput. Sci., 2009

Differentially Private Approximation Algorithms

Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar

CoRR, 2009

Approximating the Bandwidth of Caterpillars.

Uriel Feige, Kunal Talwar

Algorithmica, 2009

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

Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, Kunal Talwar

Algorithmica, 2009

Virtual Ring Routing Trends.

Dahlia Malkhi, Siddhartha Sen, Kunal Talwar, Renato Fonseca F. Werneck, Udi Wieder

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

Quincy: fair scheduling for distributed computing clusters.

Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, Andrew V. Goldberg

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

Secretary problems: weights and discounts.

Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, Kunal Talwar

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

Differentially Private Combinatorial Optimization.

Kunal Talwar, Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth

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

2008

Approximating Metric Spaces by Tree Metrics.

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

How to Complete a Doubling Metric.

Anupam Gupta, Kunal Talwar

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

A Constant Approximation Algorithm for the a prioriTraveling Salesman Problem.

David B. Shmoys, Kunal Talwar

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

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

Rina Panigrahy, Kunal Talwar, Udi Wieder

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.

Dinesh Garg, Kamal Jain, Kunal Talwar, Vijay V. Vazirani

Theor. Comput. Sci., 2007

Balanced allocations: the weighted case.

Kunal Talwar, Udi Wieder

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

The price of privacy and the limits of LP decoding.

Cynthia Dwork, Frank McSherry, Kunal Talwar

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

Hardness of routing with congestion in directed graphs.

Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar

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

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

Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, Kunal Talwar

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

Reconstructing approximate tree metrics.

Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Venugopalan Ramasubramanian, Kunal Talwar

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

Mechanism Design via Differential Privacy.

Frank McSherry, Kunal Talwar

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

Balloon Popping With Applications to Ascending Auctions.

Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Kunal Talwar

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

2006

Hardness of Low Congestion Routing in Directed Graphs.

Venkatesan Guruswami, Kunal Talwar

Electron. Colloquium Comput. Complex., 2006

Approximating unique games.

Anupam Gupta, Kunal Talwar

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

A Push-Relabel Algorithm for Approximating Degree Bounded MSTs.

Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld, Kunal Talwar

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

2005

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

Kamal Jain, Aranyak Mehta, Kunal Talwar, Vijay V. Vazirani

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

Click Fraud Resistant Methods for Learning Click-Through Rates.

Nicole Immorlica, Kamal Jain, Mohammad Mahdian, Kunal Talwar

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

On Privacy-Preserving Histograms.

Shuchi Chawla, Cynthia Dwork, Frank McSherry, Kunal Talwar

Proceedings of the UAI '05, 2005

The Generalized Deadlock Resolution Problem.

Kamal Jain, Mohammad Taghi Hajiaghayi, Kunal Talwar

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

2004

Approximating metrics by tree metrics.

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar

SIGACT News, 2004

A tight bound on approximating arbitrary metrics by tree metrics.

Jittat Fakcharoenphol, Satish Rao, Kunal Talwar

J. Comput. Syst. Sci., 2004

Bypassing the embedding: algorithms for low dimensional metrics.

Kunal Talwar

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

The complexity of pure Nash equilibria.

Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar

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

Approximate classification via earthmover metrics.

Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos

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

2003

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

Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, Éva Tardos

Internet Math., 2003

The Price of Truth: Frugality in Truthful Mechanisms.

Kunal Talwar

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.

Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar

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

An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor.

Jittat Fakcharoenphol, Kunal Talwar

Proceedings of the Approximation, 2003

Paths, Trees, and Minimum Latency Tours.

Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar

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.

Kunal Talwar

Proceedings of the Integer Programming and Combinatorial Optimization, 2002

2001

Detecting Format String Vulnerabilities with Type Qualifiers.

Umesh Shankar, Kunal Talwar, Jeffrey S. Foster, David A. Wagner

Proceedings of the 10th USENIX Security Symposium, 2001