pith. sign in

Pasin Manurangsi

Identifiers

  • name variant Pasin Manurangsi 0.60 · backfill

Papers (31)

  1. A Note on Approximability of Densest At-Least-k-Subgraph cs.DS · 2026 · author #2
  2. Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes cs.DS · 2026 · author #4
  3. Fair Allocation under Conflict Constraints cs.GT · 2026 · author #5
  4. Improved Approximation Algorithm for Maximum Balanced Biclique cs.DS · 2026 · author #1
  5. When Majority Fails: Tight Bounds for Correlation Distillation Conjectures cs.CC · 2026 · author #3
  6. Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences cs.GT · 2026 · author #1
  7. Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity cs.CR · 2026 · author #4
  8. On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic cs.CG · 2018 · author #2
  9. The Computational Complexity of Training ReLU(s) cs.CC · 2018 · author #1
  10. A Note on Max $k$-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation cs.DS · 2018 · author #1
  11. Multitasking Capacity: Hardness Results and Improved Constructions cs.DS · 2018 · author #4
  12. Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems cs.DS · 2018 · author #1
  13. A Note on Degree vs Gap of Min-Rep Label Cover and Improved Inapproximability for Connectivity Problems cs.CC · 2018 · author #1
  14. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network cs.CC · 2018 · author #2
  15. Sherali-Adams Integrality Gaps Matching the Log-Density Threshold cs.DS · 2018 · author #2
  16. Losing Treewidth by Separating Subsets cs.DS · 2018 · author #4
  17. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH cs.CC · 2018 · author #4
  18. On the Parameterized Complexity of Approximating Dominating Set cs.CC · 2017 · author #3
  19. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More cs.CC · 2017 · author #5
  20. Inapproximability of VC Dimension and Littlestone's Dimension cs.CC · 2017 · author #1
  21. Inapproximability of Maximum Biclique Problems, Minimum $k$-Cut and Densest At-Least-$k$-Subgraph from the Small Set Expansion Hypothesis cs.CC · 2017 · author #1
  22. Computing an Approximately Optimal Agreeable Set of Items cs.GT · 2017 · author #1
  23. Average whenever you meet: Opportunistic protocols for community detection cs.DM · 2017 · author #3
  24. Even $1 \times n$ Edge-Matching and Jigsaw Puzzles are Really Hard cs.CC · 2016 · author #5
  25. Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph cs.CC · 2016 · author #1
  26. An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut cs.DS · 2016 · author #3
  27. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs cs.CC · 2016 · author #1
  28. Dissection with the Fewest Pieces is Hard, Even to Approximate cs.CG · 2015 · author #5
  29. Near-Optimal UGC-hardness of Approximating Max k-CSP_R cs.CC · 2015 · author #1
  30. Approximating Dense Max 2-CSPs cs.DS · 2015 · author #1
  31. Improved Approximation Algorithms for Projection Games cs.DS · 2014 · author #1

Mentions

  • 1408.4048 #1 · backfill · confidence 0.70 Pasin Manurangsi
  • 2605.25464 #2 · arxiv_oai · confidence 0.70 Pasin Manurangsi

Frequent Coauthors