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

Email: myfirstname [at] berkeley [dot] edu

I am a third-year PhD student in the Theoretical Computer Science Group at University of California, Berkeley, where I am co-advised by Prof. Luca Trevisan and Prof. Prasad Raghavendra. My research focuses on hardness of approximation, approximation algorithms, and spectral graph theory. Prior to UC Berkeley, I received bachelor's and master's degrees from MIT, where I was very fortunate to be advised by 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) and Prof. Arnab Bhattacharyya (January 2018). I would also like to thank Bank of Thailand for their financial support during my undergraduate study.

Papers

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

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

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

Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi and Michał Włodarczyk
[arXiv]

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

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

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

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

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

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

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