Pasin Manurangsi (พศิน มนูรังษี)
Email: myfirstname [at] google [dot] comHi 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
- Excited to recieve Distinguished Senior PC Award for service at IJCAI'21
- Some recordings of my recent talks:
- On Avoiding the Union Bound When Answering Multiple Differentially Private Queries (in COLT'21): [video]
- Differentially Private Aggregation in Shuffle Model: Almost Central Accuracy in Almost a Single Message (in FORC'21): [video]
- Locally Private k-Means in One Round (in FORC'21): [video]
- The Strongish Planted Clique Hypothesis and Its Consequences (in ITCS'21): [video]
- Tight Hardness Results for Training Depth-2 ReLU Networks (in ITCS'21): [video]
- Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (in FORC'20): [video]
- Private Aggregation from Fewer Anonymous Messages (in EUROCRYPT'20): [video]
- Pure Differentially Private Summation from Anonymous Messages (in ITC'20): [video]
- Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise (in Talks on Frontiers of Parameterized Complexity): [video]
- Some recordings of recent talks given by my co-authors:
- Sample-efficient proper PAC learning with approximate differential privacy (in MIT Theory Seminar; given by Noah Golowich): [video]
- Near-tight Closure Bounds for Littlestone and Threshold Dimensions (in ALT'21; given by Noah Golowich): [video]
- On Distributed Differential Privacy and Counting Distinct Elements (in ITCS'21; given by Lijie Chen): [video]
- Algorithmic Persuasion with Evidence (in ITCS'21; given by Martin Hoefer): [video]
- Consensus Halving for Sets of Items (in WINE'20; given by Alexandros Hollender): [video]
- Nearly Optimal Robust Secret Sharing against Rushing Adversaries (in CRYPTO'20; given by Akshayaram Srinivasan): [video]
- To Close Is Easier Than To Open: Dual Parameterization To k-Median (in WAOA'20; given by Michal Wlodarczyk): [video]
- Slides from my invited talk at ALGO'19 can be found here.
Papers
Private Ad Modeling with DP-SGDCarson 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)]