Pasin Manurangsi (พศิน มนูรังษี)

Email: myfirstname [at] google [dot] com

Hi there! I have been a research scientist at Google Research since July 2019. I have a broad research interest in theoretical computer science, with emphasis on privacy, approximation algorithms & inapproximability, learning theory and computational social choice.

I received my PhD from UC Berkeley in May 2019, where I was very fortunate to be co-advised by Prof. Luca Trevisan and Prof. Prasad Raghavendra. My PhD thesis focused on hardness of approximation for problems that are neither in P nor is NP-hard; an online copy can be accessed here. I received bachelor's and master's degrees from MIT; there I worked on approximation algorithms for projection games under the wise guidance of Prof. Dana Moshkovitz. Before MIT, I was born and raised in Bangkok, Thailand where I attended Bangkok Christian College.

Acknowledgement. I am grateful to the following people for hosting and mentoring me during research visits over the years: Prof. Yury Makarychev (Summer 2016), Prof. Madhur Tulsiani (Summer 2016), Prof. Irit Dinur (Summer 2017), Prof. Eden Chlamtác (August 2017), Prof. Arnab Bhattacharyya (January 2018), Dr. Kai-Min Chung (December 2018) and Prof. Jarek Byrka (June 2019). I would also like to thank Bank of Thailand for their financial support during my undergraduate study.

Service

Misc

Papers

User-Level Differential Privacy With Few Examples Per User
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka and Chiyuan Zhang
[arXiv] [conference (NeurIPS'23, to appear)]

Optimal Unbiased Randomizers for Regression with Label Differential Privacy
Ashwinkumar Badanidiyuru, Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash Varadarajan and Chiyuan Zhang
[pdf available soon] [conference (NeurIPS'23, to appear)]

On Computing Pairwise Statistics with Local Differential Privacy
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi and Adam Sealfon
[pdf available soon] [conference (NeurIPS'23, to appear)]

Sparsity-Preserving Differentially Private Training
Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha and Chiyuan Zhang
[pdf available soon] [conference (NeurIPS'23, to appear)]

On Differentially Private Sampling from Gaussian and Product Distributions
Badih Ghazi, Xiao Hu, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (NeurIPS'23, to appear)]

Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs
Euiwoong Lee and Pasin Manurangsi
[arXiv]

Optimizing Hierarchical Queries for the Attribution Reporting API
Matthew Dawson, Badih Ghazi, Pritish Kamath, Kapil Kumar, Ravi Kumar, Bo Luan, Pasin Manurangsi, Nishanth Mundru, Harikesh Nair, Adam Sealfon and Shengyu Zhu
[arXiv]

A Note on Hardness of Computing Recursive Teaching Dimension
Pasin Manurangsi
[arXiv] [journal (IPL)]

Separating Computational and Statistical Differential Privacy (Under Plausible Assumptions)
Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (FOCS'23, to appear)]

Ticketed Learning-Unlearning Schemes
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari and Chiyuan Zhang
[arXiv] [conference (COLT'23)]

On User-Level Private Convex Optimization
Badih Ghazi, Pritish Kamath, Ravi Kumar, Raghu Meka, Pasin Manurangsi and Chiyuan Zhang
[arXiv] [conference (ICML'23)]

Differentially Private Aggregation via Imperfect Shuffling
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson and Samson Zhou
[arXiv] [conference (ITC'23)]

On Maximum Bipartite Matching with Separation
Pasin Manurangsi, Erel Segal-Halevi and Warut Suksompong
[arXiv] [journal (IPL)]

On Differentially Private Counting on Trees
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi and Kewen Wu
[arXiv] [conference (ICALP'23)]

Regression with Label Differential Privacy
Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash Varadarajan and Chiyuan Zhang
[arXiv] [conference (ICLR'23)]

Private Ad Modeling with DP-SGD
Carson Denison, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash Varadarajan and Chiyuan Zhang
[arXiv]

Differentially Private Heatmaps
Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam and Nachiappan Valliappan
[arXiv] [conference (AAAI'23)]

Differentially Private Fair Division
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (AAAI'23)]

Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique
Pasin Manurangsi
[arXiv] [conference (ITCS'23)]

Algorithms with More Granular Differential Privacy Guarantees
Badih Ghazi, Ravi Kumar, Pasin Manurangsi and Thomas Steinke
[arXiv] [conference (ITCS'23)]

Private Counting of Distinct and k-Occurring Items in Time Windows
Badih Ghazi, Ravi Kumar, Pasin Manurangsi and Jelani Nelson
[arXiv] [conference (ITCS'23)]

Differentially Private Data Release over Multiple Tables
Badih Ghazi, Xiao Hu, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (PODS'23)]

On the Fine-Grained Complexity of Approximating k-Center in Sparse Graphs
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee and Pasin Manurangsi
[conference (SOSA'23)]

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson and Yinzhan Xu
[arXiv] [conference (SODA'23)]
(The conference version is a merge of the arXiv paper linked above and another arXiv paper titled "All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights" by Justin Y. Chen, Shyam Narayanan, Yinzhan Xu.)

Large-Scale Differentially Private BERT
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar and Pasin Manurangsi
[arXiv] [journal (Findings of EMNLP'22)]

Private Isotonic Regression
Badih Ghazi, Pritish Kamath, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (NeurIPS'22)]

Anonymized Histograms in Intermediate Privacy Models
Badih Ghazi, Pritish Kamath, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (NeurIPS'22)]

Cryptographic Hardness of Learning Halfspaces with Massart Noise
Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi and Lisheng Ren
[arXiv] [conference (NeurIPS'22)]

Justifying Groups in Multiwinner Approval Voting
Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin and Warut Suksompong
[arXiv] [conference (SAGT'22)] [journal (TCS)]

Faster Privacy Accounting via Evolving Discretization
Badih Ghazi, Pritish Kamath, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (ICML'22)]

Private Robust Estimation by Stabilizing Convex Relaxations
Pravesh Kothari, Pasin Manurangsi and Ameya Velingker
[arXiv] [conference (COLT'22)]

Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (PETS'22)]

Private Aggregation of Trajectories
Badih Ghazi, Neel Kamal, Ravi Kumar, Pasin Manurangsi and Annika Zhang
[conference (PETS'22)]

Fixing Knockout Tournaments With Seeds
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (IJCAI'22)] [journal (Discrete Appl. Math.)]

Distributed, Private, Sparse Histograms in the Two-Server Model
James Bell, Adria Gascon, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Mariana Raykova and Phillipp Schoppmann
[ePrint] [conference (CCS'22)]

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee and Pasin Manurangsi
[arXiv] [conference (ICALP'22)]

Hardness of Learning a Single Neuron with Adversarial Label Noise
Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi and Lisheng Ren
[conference (AISTATS'22)]

Private Rank Aggregation in Central and Local Models
Daniel Alabi, Badih Ghazi, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (AAAI'22)]

The Price of Justified Representation
Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin and Warut Suksompong
[arXiv] [conference (AAAI'22)]

Tight Bounds for Differentially Private Anonymized Histograms
Pasin Manurangsi
[arXiv] [conference (SOSA'22)]

Multiparty Reach and Frequency Histogram:Private, Secure and Practical
Badih Ghazi, Ravi Kumar, Ben Kreuter, Pasin Manurangsi, Jiayu Peng, Evgeny Skvortsov, Yao Wang and Craig Wright
[conference (PETS'22)]

User-Level Differentially Private Learning via Correlated Sampling
Badih Ghazi, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (NeurIPS'21)]

Randomized Response with Prior and Applications to Learning with Label Differential Privacy
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi and Chiyuan Zhang
[arXiv] [conference (NeurIPS'21)]

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes Leme and Jon Schneider
[arXiv] [conference (NeurIPS'21)]

Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems
Szymon Dudycz, Pasin Manurangsi and Jan Marcinkowski
[conference (WAOA'21)]
Best Paper Award (WAOA'21)

Linear Discrepancy is Π2-Hard to Approximate
Pasin Manurangsi
[arXiv] [journal (IPL)]

On the Complexity of Fair House Allocation
Naoyuki Kamiyama, Pasin Manurangsi and Warut Suksompong
[arXiv] [journal (Operations Research Letters)]

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
Badih Ghazi, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (COLT'21)]

Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh and Amer Sinha
[arXiv] [conference (ICML'21)]

Locally Private k-Means in One Round
Alisa Chang, Badih Ghazi, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (ICML'21)]

Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (IJCAI'21)] [journal (Theor. Comput. Sci.)]

Generalized Kings and Single-Elimination Winners in Random Tournaments
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (IJCAI'21)] [journal (Auton. Agents Multi-Agent Syst.)]

Sample-efficient proper PAC learning with approximate differential privacy
Badih Ghazi, Noah Golowich, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (STOC'21)]

Robust and Private Learning of Halfspaces
Badih Ghazi, Ravi Kumar, Pasin Manurangsi and Thao Nguyen
[arXiv] [conference (AISTATS'21)]

Near-tight Closure Bounds for Littlestone and Threshold Dimensions
Badih Ghazi, Noah Golowich, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (ALT'21)]
Best Student Paper Award (ALT'21)

Tight Hardness Results for Training Depth-2 ReLU Networks
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman
[arXiv] [conference (ITCS'21)]
(This paper subsumes our earlier manuscript titled "The Computational Complexity of Training ReLU(s)".)

The Strongish Planted Clique Hypothesis and Its Consequences
Pasin Manurangsi, Aviad Rubinstein and Tselil Schramm
[arXiv] [conference (ITCS'21)]

On Distributed Differential Privacy and Counting Distinct Elements
Lijie Chen, Badih Ghazi, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (ITCS'21)]

Algorithmic Persuasion with Evidence
Martin Hoefer, Pasin Manurangsi and Alexandros Psomas
[arXiv] [conference (ITCS'21)]

Differentially Private Clustering: Tight Approximation Ratios
Badih Ghazi, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (NeurIPS'20)]

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
Ilias Diakonikolas, Daniel M. Kane and Pasin Manurangsi
[arXiv] [conference (NeurIPS'20)]

To Close Is Easier Than To Open: Dual Parameterization To k-Median
Jaroslaw Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski and Michal Wlodarczyk
[arXiv] [conference (WAOA'20)]

Consensus Halving for Sets of Items
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (WINE'20)] [journal (Math. Oper. Res.)]

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead
Badih Ghazi, Ravi Kumar, Pasin Manurangsi and Rasmus Pagh
[arXiv] [conference (ICML'20)]

Nearly Optimal Robust Secret Sharing against Rushing Adversaries
Pasin Manurangsi, Akshayaram Srinivasan and Prashant Nalini Vasudevan
[ePrint] [conference (CRYPTO'20)]

Tight Approximation for Proportional Approval Voting
Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski and Krzysztof Sornat
[conference (IJCAI'20)]

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee and Pasin Manurangsi
[arXiv] [journal (Algorithms)]

Closing Gaps in Asymptotic Fair Division
Pasin Manurangsi and Warut Suksompong
[arXiv] [journal (SIDMA)]

Pure Differentially Private Summation from Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh and Ameya Velingker
[arXiv] [conference (ITC'20)]

Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
Pasin Manurangsi
[arXiv] [conference (SODA'20)]

Private Aggregation from Fewer Anonymous Messages
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh and Ameya Velingker
[arXiv] [conference (Eurocrypt'20)]

Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
Ilias Diakonikolas, Daniel M. Kane and Pasin Manurangsi
[arXiv] [conference (NeurIPS'19)]

The Price of Fairness for Indivisible Goods
Xiaohui Bei, Xinhang Lu, Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (IJCAI'19)] [journal (Theory Comput. Syst.)]

The Computational Complexity of Training ReLU(s)
Pasin Manurangsi and Daniel Reichman
[arXiv]

Multitasking Capacity: Hardness Results and Improved Constructions
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner and Alexander Yu
[arXiv] [journal (SIDMA)]

Approximation and Hardness of Shift-Bribery
Piotr Faliszewski, Pasin Manurangsi and Krzysztof Sornat
[arXiv] [conference (AAAI'19)] [journal (Artificial Intelligence)]

When Do Envy-Free Allocations Exist?
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (AAAI'19)] [journal (SIDMA)]

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
Karthik C. S. and Pasin Manurangsi
[arXiv] [conference (ITCS'19)] [journal (Combinatorica)]

A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation
Pasin Manurangsi
[arXiv] [conference (SOSA'19)]

Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi and Michał Włodarczyk
[arXiv] [conference (SODA'19)]

A Note on Degree vs Gap of Min-Rep Label Cover and Improved Inapproximability for Connectivity Problems
Pasin Manurangsi
[arXiv] [journal (IPL)]

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
Pasin Manurangsi and Luca Trevisan
[arXiv] [conference (APPROX'18)]

Sherali-Adams Integrality Gaps Matching the Log-Density Threshold
Eden Chlamtác and Pasin Manurangsi
[arXiv] [conference (APPROX'18)]

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S. and Pasin Manurangsi
[arXiv] [conference (ICALP'18)] [journal (JACM)]
(The journal version is a merge of the ICALP'18 paper and a paper titled "Fixed-parameter Approximability of Boolean MinCSPs" by Édouard Bonnet, László Egri, Bingkai Lin, Dániel Marx.)


On the Parameterized Complexity of Approximating Dominating Set
Karthik C.S., Bundit Laekhanukit and Pasin Manurangsi
[arXiv] [conference (STOC'18)] [journal (JACM)]

ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
Irit Dinur and Pasin Manurangsi
[arXiv] [conference (ITCS'18)]

Average whenever you meet: Opportunistic protocols for community detection
Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra and Luca Trevisan
[arXiv] [conference (ESA'18)]

Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Rajesh Chitnis, Andreas Emil Feldmann and Pasin Manurangsi
[arXiv] [conference (ESA'18)] [journal (TALG)]

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai and Luca Trevisan
[arXiv] [conference (FOCS'17)] [journal (SICOMP)]

Asymptotic Existence of Fair Divisions for Groups
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (SAGT'17)] [journal (Mathematical Social Sciences)]

Inapproximability of VC Dimension and Littlestone’s Dimension
Pasin Manurangsi and Aviad Rubinstein
[arXiv] [conference (COLT'17)]

Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis
Pasin Manurangsi
[arXiv] [conference (ICALP'17)] [journal (Algorithms)]

Computing an Approximately Optimal Agreeable Set of Items
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (IJCAI'17)] [journal (Artificial Intelligence)]

Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph
Pasin Manurangsi
[arXiv] [conference (STOC'17)]
Danny Lewin Best Student Paper Award (STOC'17)

An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut
Haris Angelidakis, Yury Makarychev and Pasin Manurangsi
[arXiv] [conference (IPCO'17)]

Approximation Algorithms for Label Cover and The Log-Density Threshold
Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz and Aravindan Vijayaraghavan
[conference (SODA'17)]

A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs
Pasin Manurangsi and Prasad Raghavendra
[arXiv] [conference (ICALP'17)]

Near-Optimal UGC-hardness of Approximating Max k-CSP_R
Pasin Manurangsi, Preetum Nakkiran and Luca Trevisan
[arXiv] [conference (APPROX'16)] [journal (ToC)]

Even 1xn Edge-Matching and Jigsaw Puzzles are Really Hard
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, Anak Yodpinyanee
[arXiv] [journal (JIP)]

Dissection with the Fewest Pieces is Hard, Even to Approximate
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy and Anak Yodpinyanee
[arXiv] [conference (JCDCGG'15)]

Approximating Dense Max 2-CSPs
Pasin Manurangsi and Dana Moshkovitz
[arXiv] [conference (APPROX'15)]

Improved Approximation Algorithms for Projection Games
Pasin Manurangsi and Dana Moshkovitz
[arXiv] [conference (ESA'13)] [journal (Algorithmica)]