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

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

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
[pdf available soon] [conference (PETS'22, to appear)]

Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems
Szymon Dudycz, Pasin Manurangsi and Jan Marcinkowski
[pdf available soon] [conference (WAOA'21, to appear)]
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)]

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

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

On Deep Learning with Label Differential Privacy
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi and Chiyuan Zhang
[arXiv]

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