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

Email: myfirstname [at] berkeley [dot] edu

I am a second-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 approximation algorithms, hardness of approximation, 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.

I am grateful to Prof. Yury Makarychev and Prof. Madhur Tulsiani for supervising me during Summer 2016. I would also like to thank Bank of Thailand for their financial support during my undergraduate study.

Papers

Parameterized Approximation Algorithms for Directed Steiner Network Problems
Rajesh Chitnis, Andreas Emil Feldmann and Pasin Manurangsi
[arXiv]

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

Asymptotic Existence of Fair Divisions for Groups
Pasin Manurangsi and Warut Suksompong
[arXiv] [conference (SAGT'17, to appear)] [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)]

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