Pasin Manurangsi

Mr. Pasin Manurangsi


Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 June 2020 in Algorithms
Verified
Journal Article
Open access
PDF file
AFAndreas Emil Feldmann
Andreas Emil Feldmann
KSKarthik C. S.
Karthik C. S.
ELEuiwoong Lee
Euiwoong Lee
PMPasin Manurangsi
Pasin Manurangsi
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

17 January 2018 in Algorithms
Verified
Journal Article
Open access
PDF file
PMPasin Manurangsi
Pasin Manurangsi
The Small Set Expansion Hypothesis is a conjecture which roughly states that it is NP-hard to distinguish between a graph with a small subset of vertices whose (edge) expansion is almost zero and one in which all small subsets of vertices have expansion almost one. In this work, we prove conditional inapproximability results with essentially optimal ratios for the following graph problems based on this hypothesis: Maximum Edge Biclique, Maximum Balanced Biclique, Minimum k-Cut and Densest At-Least-k-Subgraph. Our hardness results for the two biclique problems are proved by combining a technique developed by Raghavendra, Steurer and Tulsiani to avoid locality of gadget reductions with a generalization of Bansal and Khot’s long code test whereas our results for Minimum k-Cut and Densest At-Least-k-Subgraph are shown via elementary reductions.

1 May 2020
Verified
Book Chapter
Closed access
PDF file
BGBadih Ghazi
Badih Ghazi
PMPasin Manurangsi
Pasin Manurangsi
RPRasmus Pagh
Rasmus Pagh
AVAmeya Velingker
Ameya Velingker

28 April 2020 in Combinatorica
Verified
Journal Article
Closed access
PDF file
KSKarthik C. S.
Karthik C. S.
PMPasin Manurangsi
Pasin Manurangsi

15 June 2021
Verified
Conference Paper
Open access
BGBadih Ghazi
Badih Ghazi
NGNoah Golowich
Noah Golowich
RKRavi Kumar
Ravi Kumar
PMPasin Manurangsi
Pasin Manurangsi
In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension d with approximate differential privacy is Õ(d6), ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of 2O(d) on the sample complexity. Prior to our work, finiteness of the sample complexity for privately learning a class of finite Littlestone dimension was only known for improper private learners, and the fact that our learner is proper answers another question of Bun et al., which was also asked by Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et al., we then show that the sample complexity of sanitizing a binary hypothesis class is at most polynomial in its Littlestone dimension and dual Littlestone dimension. This implies that a class is sanitizable if and only if it has finite Littlestone dimension. An important ingredient of our proofs is a new property of binary hypothesis classes that we call irreducibility, which may be of independent interest.

1 November 2022 in Mathematics of Operations Research
Verified
Journal Article
Closed access
PGPaul W. Goldberg
Paul W. Goldberg
AHAlexandros Hollender
Alexandros Hollender
AIAyumi Igarashi
Ayumi Igarashi
PMPasin Manurangsi
Pasin Manurangsi
WSWarut Suksompong
Warut Suksompong
Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented by an interval, a consensus halving with at most n cuts always exists but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting in which the resource consists of a set of items without a linear ordering. For agents with linear and additively separable utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts and show that n cuts are almost surely necessary when the agents’ utilities are randomly generated. On the other hand, we show that, for a simple class of monotonic utilities, the problem already becomes polynomial parity argument, directed version–hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, with which we wish to divide the resource into k parts in possibly unequal ratios and provide some consequences of our results on the problem of computing small agreeable sets.