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.

Misc

Papers

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, to appear)]

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

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

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

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

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

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

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, to appear)]
(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, to appear)]

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

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

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

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

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)]

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, to appear)]

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)]