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

Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph
Pasin Manurangsi
[arXiv] [conference (STOC'17, to appear)]

An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut
Haris Angelidakis, Yury Makarychev and Pasin Manurangsi
[arXiv] [conference (IPCO'17, to appear)]

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]

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]

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