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 Rank Aggregation in Central and Local Models
Daniel Alabi, Badih Ghazi, Ravi Kumar and Pasin Manurangsi
[arXiv] [conference (AAAI'22, to appear)]

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

Private Robust Estimation by Stabilizing Convex Relaxations
Pravesh Kothari, Pasin Manurangsi and Ameya Velingker
[arXiv]

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

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

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

Large-Scale Differentially Private BERT
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar and Pasin Manurangsi
[arXiv]

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

Generalized Kings and Single-Elimination Winners in Random Tournaments
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (IJCAI'21)]

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

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

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