Pasin Manurangsi

307 papers A* 67A 22B 7Journal 192Unranked 18

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Computational Hardness of Private Coreset. CoRR Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi
2026	J	`jnl`	Denoising the US Census: Succinct Block Hierarchical Regression. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon
2026	A	`conf`	Discrepancy Beyond Additive Functions with Applications to Fair Division (Extended Abstract). ITCS Alexandros Hollender, Pasin Manurangsi, Raghu Meka, Warut Suksompong
2026	A*	`conf`	Fair Allocation of Indivisible Goods with Variable Groups. AAAI Paul Gölz, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
2026	A*	`conf`	Improved Differentially Private Algorithms for Rank Aggregation. AAAI Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn, Phanu Vajanopath
2026	J	`jnl`	Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms. CoRR Alessandro Epasto, Xin Lyu, Pasin Manurangsi
2026	J	`jnl`	Natural Privacy Filters Are Not Always Free: A Characterization of Free Natural Filters. CoRR Matthew Regehr, Bingshan Hu, Ethan Leeman, Pasin Manurangsi, Pierre Tholoniat, Mathias Lécuyer
2026	A	`conf`	On the PTAS Complexity of Multidimensional Knapsack. ITCS Ilan Doron-Arad, Ariel Kulik, Pasin Manurangsi
2026	J	`jnl`	Optimal partition selection with Rényi differential privacy. CoRR Charlie Harrison, Pasin Manurangsi
2026	J	`jnl`	The Price of Privacy For Approximating Max-CSP. CoRR Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi, Akbar Rafiey, Phanu Vajanopath, Zongrui Zou
2026	—	`conf`	Tight Lower Bound for Multicolor Discrepancy. SOSA Pasin Manurangsi, Raghu Meka
2025	A*	`conf`	Asymptotic Analysis of Weighted Fair Division. IJCAI Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama
2025	J	`jnl`	Asymptotic Analysis of Weighted Fair Division. CoRR Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama
2025	A*	`conf`	Asymptotic Fair Division: Chores Are Easier Than Goods. IJCAI Pasin Manurangsi, Warut Suksompong
2025	J	`jnl`	Asymptotic Fair Division: Chores Are Easier Than Goods. CoRR Pasin Manurangsi, Warut Suksompong
2025	J	`jnl`	Asymptotic analysis of weighted fair division. Theor. Comput. Sci. Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama
2025	A	`conf`	Balls-and-Bins Sampling for DP-SGD. AISTATS Lynn Chua, Badih Ghazi, Charlie Harrison, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2025	J	`jnl`	Complexity of round-robin allocation with potentially noisy queries. Inf. Comput. Zihan Li, Pasin Manurangsi, Jonathan Scarlett, Warut Suksompong
2025	A	`conf`	Differential Privacy on Trust Graphs. ITCS Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Serena Wang
2025	J	`jnl`	Differentially private fair division. Artif. Intell. Pasin Manurangsi, Warut Suksompong
2025	J	`jnl`	Discrepancy Beyond Additive Functions with Applications to Fair Division. CoRR Alexandros Hollender, Pasin Manurangsi, Raghu Meka, Warut Suksompong
2025	A*	`conf`	Dividing Conflicting Items Fairly. IJCAI Ayumi Igarashi, Pasin Manurangsi, Hirotaka Yoneda
2025	J	`jnl`	Dividing Conflicting Items Fairly. CoRR Ayumi Igarashi, Pasin Manurangsi, Hirotaka Yoneda
2025	J	`jnl`	Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms. CoRR Charlie Harrison, Pasin Manurangsi
2025	J	`jnl`	Fair Allocation of Indivisible Goods with Variable Groups. CoRR Paul Gölz, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
2025	J	`jnl`	How Unique is Whose Web Browser? The role of demographics in browser fingerprinting among US users. Proc. Priv. Enhancing Technol. Alex Berke, Badih Ghazi, Enrico Bacis, Pritish Kamath, Ravi Kumar, Robin Lassonde, Pasin Manurangsi, Umar Syed
2025	J	`jnl`	Improved Differentially Private Algorithms for Rank Aggregation. CoRR Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn, Phanu Vajanopath
2025	J	`jnl`	Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: Greedy strikes back. Theor. Comput. Sci. Pasin Manurangsi
2025	J	`jnl`	Improved lower bound for differentially private facility location. Inf. Process. Lett. Pasin Manurangsi
2025	—	`conf`	Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High ε Regime. FORC Charlie Harrison, Pasin Manurangsi
2025	J	`jnl`	Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High ϵ Regime. CoRR Charlie Harrison, Pasin Manurangsi
2025	J	`jnl`	Linear-Time User-Level DP-SCO via Robust Statistics. CoRR Badih Ghazi, Ravi Kumar, Daogao Liu, Pasin Manurangsi
2025	J	`jnl`	Nearly-Optimal Private Selection via Gaussian Mechanism. CoRR Ethan Leeman, Pasin Manurangsi
2025	J	`jnl`	On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP. Algorithmica Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2025	J	`jnl`	On the Differential Privacy and Interactivity of Privacy Sandbox Reports. Proc. Priv. Enhancing Technol. Badih Ghazi, Charlie Harrison, Arpana Hosabettu, Pritish Kamath, Alexander Knop, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Mariana Raykova, Vikas Sahu, Phillipp Schoppmann
2025	J	`jnl`	Ordinal maximin guarantees for group fair division. Theor. Comput. Sci. Pasin Manurangsi, Warut Suksompong
2025	A*	`conf`	PREM: Privately Answering Statistical Queries with Relative Error. COLT Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, Sushant Sachdeva
2025	J	`jnl`	PREM: Privately Answering Statistical Queries with Relative Error. CoRR Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, Sushant Sachdeva
2025	J	`jnl`	Private Hyperparameter Tuning with Ex-Post Guarantee. CoRR Badih Ghazi, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, Chiyuan Zhang
2025	J	`jnl`	Tight Lower Bound for Multicolor Discrepancy. CoRR Pasin Manurangsi, Raghu Meka
2025	A*	`conf`	Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy. ICLR Yangsibo Huang, Daogao Liu, Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Milad Nasr, Amer Sinha, Chiyuan Zhang
2025	J	`jnl`	Urania: Differentially Private Insights into AI Use. CoRR Daogao Liu, Edith Cohen, Badih Ghazi, Peter Kairouz, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, Adam Sealfon, Da Yu, Chiyuan Zhang
2025	J	`jnl`	VaultGemma: A Differentially Private Gemma Model. CoRR Amer Sinha, Thomas Mesnard, Ryan McKenna, Daogao Liu, Christopher A. Choquette-Choo, Yangsibo Huang, Da Yu, Georgios Kaissis, Zachary Charles, Ruibo Liu, Lynn Chua, Pritish Kamath, Pasin Manurangsi, Steve He, Chiyuan Zhang, Badih Ghazi, Borja de Balle Pigem, Prem Eruvbetine, Tris Warkentin, Armand Joulin, Ravi Kumar
2024	J	`jnl`	A note on hardness of computing recursive teaching dimension. Inf. Process. Lett. Pasin Manurangsi
2024	J	`jnl`	Algorithmic Persuasion with Evidence. ACM Trans. Economics and Comput. Martin Hoefer, Pasin Manurangsi, Alexandros Psomas
2024	J	`jnl`	Balls-and-Bins Sampling for DP-SGD. CoRR Lynn Chua, Badih Ghazi, Charlie Harrison, Ethan Leeman, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2024	B	`conf`	Complexity of Round-Robin Allocation with Potentially Noisy Queries. SAGT Zihan Li, Pasin Manurangsi, Jonathan Scarlett, Warut Suksompong
2024	J	`jnl`	Complexity of Round-Robin Allocation with Potentially Noisy Queries. CoRR Zihan Li, Pasin Manurangsi, Jonathan Scarlett, Warut Suksompong
2024	J	`jnl`	Crosslingual Capabilities and Knowledge Barriers in Multilingual Large Language Models. CoRR Lynn Chua, Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chulin Xie, Chiyuan Zhang
2024	J	`jnl`	Differential Privacy on Trust Graphs. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Serena Wang
2024	J	`jnl`	Differentially Private Ad Conversion Measurement. CoRR John Delaney, Badih Ghazi, Charlie Harrison, Christina Ilvento, Ravi Kumar, Pasin Manurangsi, Martin Pal, Karthik Prabhakar, Mariana Raykova
2024	J	`jnl`	Differentially Private Ad Conversion Measurement. Proc. Priv. Enhancing Technol. John Delaney, Badih Ghazi, Charlie Harrison, Christina Ilvento, Ravi Kumar, Pasin Manurangsi, Martin Pál, Karthik Prabhakar, Mariana Raykova
2024	A*	`conf`	Differentially Private Optimization with Sparse Gradients. NeurIPS Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2024	J	`jnl`	Differentially Private Optimization with Sparse Gradients. CoRR Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2024	J	`jnl`	Erratum: Multitasking Capacity: Hardness Results and Improved Constructions. SIAM J. Discret. Math. Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner
2024	J	`jnl`	Fine Grained Lower Bounds for Multidimensional Knapsack. CoRR Ilan Doron-Arad, Ariel Kulik, Pasin Manurangsi
2024	A	`conf`	Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. ITCS Euiwoong Lee, Pasin Manurangsi
2024	A*	`conf`	How Private are DP-SGD Implementations? ICML Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2024	J	`jnl`	How Private is DP-SGD? CoRR Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2024	J	`jnl`	How Unique is Whose Web Browser? The role of demographics in browser fingerprinting among US users. CoRR Alex Berke, Enrico Bacis, Badih Ghazi, Pritish Kamath, Ravi Kumar, Robin Lassonde, Pasin Manurangsi, Umar Syed
2024	J	`jnl`	Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back. CoRR Pasin Manurangsi
2024	J	`jnl`	Improved Lower Bound for Differentially Private Facility Location. CoRR Pasin Manurangsi
2024	A*	`conf`	Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization. ICML Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon
2024	J	`jnl`	Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon
2024	A*	`conf`	LabelDP-Pro: Learning with Label Differential Privacy via Projections. ICLR Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Chiyuan Zhang
2024	J	`jnl`	Mind the Privacy Unit! User-Level Differential Privacy for Language Model Fine-Tuning. CoRR Lynn Chua, Badih Ghazi, Yangsibo Huang, Pritish Kamath, Daogao Liu, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2024	J	`jnl`	On Computing Pairwise Statistics with Local Differential Privacy. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon
2024	A*	`conf`	On Convex Optimization with Semi-Sensitive Features. COLT Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
2024	J	`jnl`	On Convex Optimization with Semi-Sensitive Features. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
2024	B	`conf`	On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP. IPEC Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2024	J	`jnl`	On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP. CoRR Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2024	J	`jnl`	On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. Electron. Colloquium Comput. Complex. Karthik C. S., Pasin Manurangsi
2024	J	`jnl`	On the Differential Privacy and Interactivity of Privacy Sandbox Reports. CoRR Badih Ghazi, Charlie Harrison, Arpana Hosabettu, Pritish Kamath, Alexander Knop, S. Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Vikas Sahu
2024	A*	`conf`	Ordinal Maximin Guarantees for Group Fair Division. IJCAI Pasin Manurangsi, Warut Suksompong
2024	J	`jnl`	Ordinal Maximin Guarantees for Group Fair Division. CoRR Pasin Manurangsi, Warut Suksompong
2024	—	`conf`	Privacy in Web Advertising: Analytics and Modeling. WWW (Companion Volume) Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2024	A	`conf`	Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient. ITC Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2024	A*	`conf`	Scalable DP-SGD: Shuffling vs. Poisson Subsampling. NeurIPS Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2024	J	`jnl`	Scalable DP-SGD: Shuffling vs. Poisson Subsampling. CoRR Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2024	J	`jnl`	Summary Reports Optimization in the Privacy Sandbox Attribution Reporting API. Proc. Priv. Enhancing Technol. Hidayet Aksu, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon, Avinash V. Varadarajan
2024	J	`jnl`	The Price of Justified Representation. ACM Trans. Economics and Comput. Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong
2024	—	`conf`	Training Differentially Private Ad Prediction Models With Semi-Sensitive Features. AdKDD@KDD Lynn Chua, Qiliang Cui, Badih Ghazi, Charlie Harrison, Pritish Kamath, Walid Krichene, Ravi Kumar, Pasin Manurangsi, Nicolas Mayoraz, Hema Venkata Krishna Giri Narra, Steffen Rendle, Amer Sinha, Avinash V. Varadarajan, Chiyuan Zhang
2024	J	`jnl`	Training Differentially Private Ad Prediction Models with Semi-Sensitive Features. CoRR Lynn Chua, Qiliang Cui, Badih Ghazi, Charlie Harrison, Pritish Kamath, Walid Krichene, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash V. Varadarajan, Chiyuan Zhang
2024	J	`jnl`	Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy. CoRR Yangsibo Huang, Daogao Liu, Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Milad Nasr, Amer Sinha, Chiyuan Zhang
2023	J	`jnl`	A Note on Hardness of Computing Recursive Teaching Dimension. CoRR Pasin Manurangsi
2023	A	`conf`	Algorithms with More Granular Differential Privacy Guarantees. ITCS Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke
2023	A	`conf`	Differentially Private Aggregation via Imperfect Shuffling. ITC Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou
2023	J	`jnl`	Differentially Private Aggregation via Imperfect Shuffling. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou
2023	A*	`conf`	Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. SODA Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu
2023	A*	`conf`	Differentially Private Data Release over Multiple Tables. PODS Badih Ghazi, Xiao Hu, Ravi Kumar, Pasin Manurangsi
2023	J	`jnl`	Differentially Private Data Release over Multiple Tables. CoRR Badih Ghazi, Xiao Hu, Ravi Kumar, Pasin Manurangsi
2023	A*	`conf`	Differentially Private Fair Division. AAAI Pasin Manurangsi, Warut Suksompong
2023	A*	`conf`	Differentially Private Heatmaps. AAAI Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam, Nachiappan Valliappan
2023	J	`jnl`	Fixing knockout tournaments with seeds. Discret. Appl. Math. Pasin Manurangsi, Warut Suksompong
2023	J	`jnl`	Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. CoRR Euiwoong Lee, Pasin Manurangsi
2023	A	`conf`	Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique. ITCS Pasin Manurangsi
2023	J	`jnl`	Justifying groups in multiwinner approval voting. Theor. Comput. Sci. Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong
2023	A*	`conf`	On Computing Pairwise Statistics with Local Differential Privacy. NeurIPS Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon
2023	A*	`conf`	On Differentially Private Counting on Trees. ICALP Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Kewen Wu
2023	A*	`conf`	On Differentially Private Sampling from Gaussian and Product Distributions. NeurIPS Badih Ghazi, Xiao Hu, Ravi Kumar, Pasin Manurangsi
2023	J	`jnl`	On Differentially Private Sampling from Gaussian and Product Distributions. CoRR Badih Ghazi, Xiao Hu, Ravi Kumar, Pasin Manurangsi
2023	J	`jnl`	On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. CoRR Karthik C. S., Pasin Manurangsi
2023	J	`jnl`	On Maximum Bipartite Matching with Separation. CoRR Pasin Manurangsi, Erel Segal-Halevi, Warut Suksompong
2023	A*	`conf`	On User-Level Private Convex Optimization. ICML Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
2023	J	`jnl`	On User-Level Private Convex Optimization. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Raghu Meka, Pasin Manurangsi, Chiyuan Zhang
2023	J	`jnl`	On maximum bipartite matching with separation. Inf. Process. Lett. Pasin Manurangsi, Erel Segal-Halevi, Warut Suksompong
2023	—	`conf`	On the Fine-Grained Complexity of Approximating SOSA Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2023	A*	`conf`	Optimal Unbiased Randomizers for Regression with Label Differential Privacy. NeurIPS Ashwinkumar Badanidiyuru Varadaraja, Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash V. Varadarajan, Chiyuan Zhang
2023	J	`jnl`	Optimal Unbiased Randomizers for Regression with Label Differential Privacy. CoRR Ashwinkumar Badanidiyuru, Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash V. Varadarajan, Chiyuan Zhang
2023	—	`conf`	Optimizing Hierarchical Queries for the Attribution Reporting API. AdKDD@KDD Matthew Dawson, Badih Ghazi, Pritish Kamath, Kapil Kumar, Ravi Kumar, Bo Luan, Pasin Manurangsi, Nishanth Mundru, Harikesh Nair, Adam Sealfon, Shengyu Zhu
2023	J	`jnl`	Optimizing Hierarchical Queries for the Attribution Reporting API. CoRR Matthew Dawson, Badih Ghazi, Pritish Kamath, Kapil Kumar, Ravi Kumar, Bo Luan, Pasin Manurangsi, Nishanth Mundru, Harikesh Nair, Adam Sealfon, Shengyu Zhu
2023	A*	`conf`	Privacy in Advertising: Analytics and Modeling. KDD Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2023	—	`conf`	Private Ad Modeling with DP-SGD. AdKDD@KDD Carson Denison, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash V. Varadarajan, Chiyuan Zhang
2023	A	`conf`	Private Counting of Distinct and k-Occurring Items in Time Windows. ITCS Badih Ghazi, Ravi Kumar, Jelani Nelson, Pasin Manurangsi
2023	J	`jnl`	Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2023	A*	`conf`	Regression with Label Differential Privacy. ICLR Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash V. Varadarajan, Chiyuan Zhang
2023	J	`jnl`	Separating Computational and Statistical Differential Privacy (Under Plausible Assumptions). CoRR Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2023	A*	`conf`	Sparsity-Preserving Differentially Private Training of Large Embedding Models. NeurIPS Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2023	J	`jnl`	Sparsity-Preserving Differentially Private Training of Large Embedding Models. CoRR Badih Ghazi, Yangsibo Huang, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang
2023	J	`jnl`	Summary Reports Optimization in the Privacy Sandbox Attribution Reporting API. CoRR Hidayet Aksu, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Adam Sealfon, Avinash V. Varadarajan
2023	A*	`conf`	Ticketed Learning-Unlearning Schemes. COLT Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, Chiyuan Zhang
2023	J	`jnl`	Ticketed Learning-Unlearning Schemes. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, Chiyuan Zhang
2023	A*	`conf`	Towards Separating Computational and Statistical Differential Privacy. FOCS Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2023	A*	`conf`	User-Level Differential Privacy With Few Examples Per User. NeurIPS Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
2023	J	`jnl`	User-Level Differential Privacy With Few Examples Per User. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
2022	J	`jnl`	Algorithms with More Granular Differential Privacy Guarantees. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke
2022	J	`jnl`	Almost envy-freeness for groups: Improved bounds via discrepancy theory. Theor. Comput. Sci. Pasin Manurangsi, Warut Suksompong
2022	A*	`conf`	Anonymized Histograms in Intermediate Privacy Models. NeurIPS Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022	J	`jnl`	Anonymized Histograms in Intermediate Privacy Models. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022	J	`jnl`	Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions. CoRR Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022	J	`jnl`	Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions. Proc. Priv. Enhancing Technol. Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022	J	`jnl`	Consensus Halving for Sets of Items. Math. Oper. Res. Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
2022	A*	`conf`	Cryptographic Hardness of Learning Halfspaces with Massart Noise. NeurIPS Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng Ren
2022	J	`jnl`	Cryptographic Hardness of Learning Halfspaces with Massart Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi, Lisheng Ren
2022	J	`jnl`	Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson
2022	J	`jnl`	Differentially Private Fair Division. CoRR Pasin Manurangsi, Warut Suksompong
2022	J	`jnl`	Differentially Private Heatmaps. CoRR Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam, Nachiappan Valliappan
2022	A*	`conf`	Distributed, Private, Sparse Histograms in the Two-Server Model. CCS James Bell, Adrià Gascón, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Mariana Raykova, Phillipp Schoppmann
2022	J	`jnl`	Distributed, Private, Sparse Histograms in the Two-Server Model. IACR Cryptol. ePrint Arch. James Bell, Adrià Gascón, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Mariana Raykova, Phillipp Schoppmann
2022	A*	`conf`	Faster Privacy Accounting via Evolving Discretization. ICML Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022	J	`jnl`	Faster Privacy Accounting via Evolving Discretization. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022	A*	`conf`	Fixing Knockout Tournaments With Seeds. IJCAI Pasin Manurangsi, Warut Suksompong
2022	J	`jnl`	Fixing Knockout Tournaments With Seeds. CoRR Pasin Manurangsi, Warut Suksompong
2022	J	`jnl`	Generalized kings and single-elimination winners in random tournaments. Auton. Agents Multi Agent Syst. Pasin Manurangsi, Warut Suksompong
2022	A	`conf`	Hardness of Learning a Single Neuron with Adversarial Label Noise. AISTATS Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi, Lisheng Ren
2022	A*	`conf`	Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. ICALP Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2022	J	`jnl`	Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. CoRR Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, Pasin Manurangsi
2022	J	`jnl`	Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique. CoRR Pasin Manurangsi
2022	B	`conf`	Justifying Groups in Multiwinner Approval Voting. SAGT Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong
2022	—	`conf`	Large-Scale Differentially Private BERT. EMNLP (Findings) Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, Pasin Manurangsi
2022	J	`jnl`	Multiparty Reach and Frequency Histogram: Private, Secure, and Practical. Proc. Priv. Enhancing Technol. Badih Ghazi, Ben Kreuter, Ravi Kumar, Pasin Manurangsi, Jiayu Peng, Evgeny Skvortsov, Yao Wang, Craig Wright
2022	J	`jnl`	Near-Optimal NP-Hardness of Approximating Max k-CSP Theory Comput. Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
2022	J	`jnl`	On Differentially Private Counting on Trees. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Kewen Wu
2022	J	`jnl`	Private Ad Modeling with DP-SGD. CoRR Carson Denison, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash V. Varadarajan, Chiyuan Zhang
2022	J	`jnl`	Private Aggregation of Trajectories. Proc. Priv. Enhancing Technol. Badih Ghazi, Neel Kamal, Ravi Kumar, Pasin Manurangsi, Annika Zhang
2022	J	`jnl`	Private Counting of Distinct and k-Occurring Items in Time Windows. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson
2022	A*	`conf`	Private Isotonic Regression. NeurIPS Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022	J	`jnl`	Private Isotonic Regression. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
2022	A*	`conf`	Private Rank Aggregation in Central and Local Models. AAAI Daniel Alabi, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2022	A*	`conf`	Private Robust Estimation by Stabilizing Convex Relaxations. COLT Pravesh Kothari, Pasin Manurangsi, Ameya Velingker
2022	J	`jnl`	Regression with Label Differential Privacy. CoRR Badih Ghazi, Pritish Kamath, Ravi Kumar, Ethan Leeman, Pasin Manurangsi, Avinash V. Varadarajan, Chiyuan Zhang
2022	A*	`conf`	The Price of Justified Representation. AAAI Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong
2022	—	`conf`	Tight Bounds for Differentially Private Anonymized Histograms. SOSA Pasin Manurangsi
2021	A	`conf`	Algorithmic Persuasion with Evidence. ITCS Martin Hoefer, Pasin Manurangsi, Alexandros Psomas
2021	A*	`conf`	Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory. IJCAI Pasin Manurangsi, Warut Suksompong
2021	J	`jnl`	Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory. CoRR Pasin Manurangsi, Warut Suksompong
2021	J	`jnl`	Approximation and hardness of Shift-Bribery. Artif. Intell. Piotr Faliszewski, Pasin Manurangsi, Krzysztof Sornat
2021	J	`jnl`	Closing Gaps in Asymptotic Fair Division. SIAM J. Discret. Math. Pasin Manurangsi, Warut Suksompong
2021	A*	`conf`	Contextual Recommendations and Low-Regret Cutting-Plane Algorithms. NeurIPS Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes Leme, Jon Schneider
2021	J	`jnl`	Contextual Recommendations and Low-Regret Cutting-Plane Algorithms. CoRR Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias, Pasin Manurangsi, Renato Paes Leme, Jon Schneider
2021	A*	`conf`	Deep Learning with Label Differential Privacy. NeurIPS Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Chiyuan Zhang
2021	A*	`conf`	Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message. ICML Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Amer Sinha
2021	J	`jnl`	Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Amer Sinha
2021	A*	`conf`	Generalized Kings and Single-Elimination Winners in Random Tournaments. IJCAI Pasin Manurangsi, Warut Suksompong
2021	J	`jnl`	Generalized Kings and Single-Elimination Winners in Random Tournaments. CoRR Pasin Manurangsi, Warut Suksompong
2021	J	`jnl`	Google COVID-19 Vaccination Search Insights: Anonymization Process Description. CoRR Shailesh Bavadekar, Adam Boulanger, John Davis, Damien Desfontaines, Evgeniy Gabrilovich, Krishna Gadepalli, Badih Ghazi, Tague Griffith, Jai Prakash Gupta, Chaitanya Kamath, Dennis Kraft, Ravi Kumar, Akim Kumok, Yael Mayer, Pasin Manurangsi, Arti Patankar, Irippuge Milinda Perera, Chris Scott, Tomer Shekel, Benjamin Miller, Karen Smith, Charlotte Stanton, Mimi Sun, Mark Young, Gregory Wellenius
2021	J	`jnl`	Justifying Groups in Multiwinner Approval Voting. CoRR Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong
2021	J	`jnl`	Large-Scale Differentially Private BERT. CoRR Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, Pasin Manurangsi
2021	J	`jnl`	Linear Discrepancy is Π CoRR Pasin Manurangsi
2021	J	`jnl`	Linear discrepancy is Π Inf. Process. Lett. Pasin Manurangsi
2021	A*	`conf`	Locally Private k-Means in One Round. ICML Alisa Chang, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2021	J	`jnl`	Locally Private k-Means in One Round. CoRR Alisa Chang, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2021	B	`conf`	Near-tight closure b ounds for the Littlestone and threshold dimensions. ALT Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
2021	A*	`conf`	On Avoiding the Union Bound When Answering Multiple Differentially Private Queries. COLT Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2021	J	`jnl`	On Deep Learning with Label Differential Privacy. CoRR Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Chiyuan Zhang
2021	A	`conf`	On Distributed Differential Privacy and Counting Distinct Elements. ITCS Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2021	J	`jnl`	On the Complexity of Fair House Allocation. CoRR Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong
2021	J	`jnl`	On the complexity of fair house allocation. Oper. Res. Lett. Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong
2021	J	`jnl`	Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. ACM Trans. Algorithms Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi
2021	J	`jnl`	Parameterized Intractability of Even Set and Shortest Vector Problem. J. ACM Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
2021	J	`jnl`	Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh
2021	J	`jnl`	Private Rank Aggregation in Central and Local Models. CoRR Daniel Alabi, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2021	J	`jnl`	Private Robust Estimation by Stabilizing Convex Relaxations. CoRR Pravesh K. Kothari, Pasin Manurangsi, Ameya Velingker
2021	A	`conf`	Robust and Private Learning of Halfspaces. AISTATS Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thao Nguyen
2021	A*	`conf`	Sample-efficient proper PAC learning with approximate differential privacy. STOC Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
2021	J	`jnl`	The Price of Fairness for Indivisible Goods. Theory Comput. Syst. Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong
2021	J	`jnl`	The Price of Justified Representation. CoRR Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong
2021	A	`conf`	The Strongish Planted Clique Hypothesis and Its Consequences. ITCS Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
2021	J	`jnl`	Tight Bounds for Differentially Private Anonymized Histograms. CoRR Pasin Manurangsi
2021	A	`conf`	Tight Hardness Results for Training Depth-2 ReLU Networks. ITCS Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, Daniel Reichman
2021	B	`conf`	Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems. WAOA Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski
2021	A*	`conf`	User-Level Differentially Private Learning via Correlated Sampling. NeurIPS Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2021	J	`jnl`	User-Level Private Learning via Correlated Sampling. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2020	J	`jnl`	A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2020	J	`jnl`	A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. CoRR Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2020	J	`jnl`	A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Electron. Colloquium Comput. Complex. Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi
2020	J	`jnl`	Algorithmic Persuasion with Evidence. CoRR Martin Hoefer, Pasin Manurangsi, Alexandros Psomas
2020	J	`jnl`	Closing Gaps in Asymptotic Fair Division. CoRR Pasin Manurangsi, Warut Suksompong
2020	—	`conf`	Consensus Halving for Sets of Items. WINE Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
2020	J	`jnl`	Consensus Halving for Sets of Items. CoRR Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi, Pasin Manurangsi, Warut Suksompong
2020	A*	`conf`	Differentially Private Clustering: Tight Approximation Ratios. NeurIPS Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2020	J	`jnl`	Differentially Private Clustering: Tight Approximation Ratios. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2020	J	`jnl`	From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. SIAM J. Comput. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2020	J	`jnl`	Multitasking Capacity: Hardness Results and Improved Constructions. SIAM J. Discret. Math. Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku
2020	J	`jnl`	Near-tight closure bounds for Littlestone and threshold dimensions. CoRR Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
2020	—	`conf`	Nearly Optimal Robust Secret Sharing Against Rushing Adversaries. CRYPTO (3) Pasin Manurangsi, Akshayaram Srinivasan, Prashant Nalini Vasudevan
2020	J	`jnl`	On Avoiding the Union Bound When Answering Multiple Differentially Private Queries. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2020	J	`jnl`	On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. Comb. Karthik C. S., Pasin Manurangsi
2020	J	`jnl`	On Distributed Differential Privacy and Counting Distinct Elements. CoRR Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
2020	—	`conf`	Private Aggregation from Fewer Anonymous Messages. EUROCRYPT (2) Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
2020	A*	`conf`	Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead. ICML Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh
2020	A	`conf`	Pure Differentially Private Summation from Anonymous Messages. ITC Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
2020	J	`jnl`	Pure Differentially Private Summation from Anonymous Messages. CoRR Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
2020	J	`jnl`	Robust and Private Learning of Halfspaces. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thao Nguyen
2020	J	`jnl`	Sample-efficient proper PAC learning with approximate differential privacy. CoRR Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi
2020	A*	`conf`	The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise. NeurIPS Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
2020	J	`jnl`	The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise. CoRR Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
2020	J	`jnl`	The Strongish Planted Clique Hypothesis and Its Consequences. CoRR Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
2020	A*	`conf`	Tight Approximation for Proportional Approval Voting. IJCAI Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Krzysztof Sornat
2020	J	`jnl`	Tight Hardness Results for Training Depth-2 ReLU Networks. CoRR Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, Daniel Reichman
2020	A*	`conf`	Tight Running Time Lower Bounds for Strong Inapproximability of Maximum SODA Pasin Manurangsi
2020	B	`conf`	To Close Is Easier Than To Open: Dual Parameterization To k-Median. WAOA Jaroslaw Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Michal Wlodarczyk
2020	J	`jnl`	To Close Is Easier Than To Open: Dual Parameterization To k-Median. CoRR Jaroslaw Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Michal Wlodarczyk
2020	J	`jnl`	When Do Envy-Free Allocations Exist? SIAM J. Discret. Math. Pasin Manurangsi, Warut Suksompong
2019	—	`conf`	A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. SOSA Pasin Manurangsi
2019	J	`jnl`	A note on degree vs gap of Min-Rep Label Cover and improved inapproximability for connectivity problems. Inf. Process. Lett. Pasin Manurangsi
2019	A*	`conf`	Approximation and Hardness of Shift-Bribery. AAAI Piotr Faliszewski, Pasin Manurangsi, Krzysztof Sornat
2019	J	`jnl`	Approximation and Hardness of Shift-Bribery. CoRR Piotr Faliszewski, Pasin Manurangsi, Krzysztof Sornat
2019	—	`—`	Approximation and Hardness: Beyond P and NP. Pasin Manurangsi
2019	J	`jnl`	Computing a small agreeable set of indivisible items. Artif. Intell. Pasin Manurangsi, Warut Suksompong
2019	A*	`conf`	Losing Treewidth by Separating Subsets. SODA Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk
2019	J	`jnl`	Nearly Optimal Robust Secret Sharing against Rushing Adversaries. IACR Cryptol. ePrint Arch. Pasin Manurangsi, Akshayaram Srinivasan, Prashant Nalini Vasudevan
2019	A*	`conf`	Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin. NeurIPS Ilias Diakonikolas, Daniel Kane, Pasin Manurangsi
2019	J	`jnl`	Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin. CoRR Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
2019	A	`conf`	On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. ITCS Karthik C. S., Pasin Manurangsi
2019	J	`jnl`	On the Parameterized Complexity of Approximating Dominating Set. J. ACM Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2019	J	`jnl`	Parameterized Intractability of Even Set and Shortest Vector Problem. CoRR Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
2019	J	`jnl`	Parameterized Intractability of Even Set and Shortest Vector Problem. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx
2019	J	`jnl`	Private Aggregation from Fewer Anonymous Messages. CoRR Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker
2019	A*	`conf`	The Price of Fairness for Indivisible Goods. IJCAI Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong
2019	J	`jnl`	The Price of Fairness for Indivisible Goods. CoRR Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, Warut Suksompong
2019	J	`jnl`	Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem). CoRR Pasin Manurangsi
2019	A*	`conf`	When Do Envy-Free Allocations Exist? AAAI Pasin Manurangsi, Warut Suksompong
2018	J	`jnl`	A Note on Degree vs Gap of Min-Rep Label Cover and Improved Inapproximability for Connectivity Problems. CoRR Pasin Manurangsi
2018	J	`jnl`	A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation. CoRR Pasin Manurangsi
2018	A	`conf`	Average Whenever You Meet: Opportunistic Protocols for Community Detection. ESA Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
2018	A	`conf`	ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. ITCS Irit Dinur, Pasin Manurangsi
2018	J	`jnl`	ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. CoRR Irit Dinur, Pasin Manurangsi
2018	J	`jnl`	ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. Electron. Colloquium Comput. Complex. Irit Dinur, Pasin Manurangsi
2018	J	`jnl`	Inapproximability of Maximum Biclique Problems, Minimum Algorithms Pasin Manurangsi
2018	J	`jnl`	Losing Treewidth by Separating Subsets. CoRR Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michal Wlodarczyk
2018	—	`conf`	Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut. APPROX-RANDOM Pasin Manurangsi, Luca Trevisan
2018	J	`jnl`	Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems. CoRR Pasin Manurangsi, Luca Trevisan
2018	J	`jnl`	Multitasking Capacity: Hardness Results and Improved Constructions. CoRR Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku
2018	J	`jnl`	On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. CoRR Karthik C. S., Pasin Manurangsi
2018	J	`jnl`	On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. Electron. Colloquium Comput. Complex. Karthik C. S., Pasin Manurangsi
2018	A*	`conf`	On the parameterized complexity of approximating dominating set. STOC Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2018	A	`conf`	Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. ESA Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi
2018	A*	`conf`	Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. ICALP Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
2018	J	`jnl`	Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. CoRR Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
2018	J	`jnl`	Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi
2018	—	`conf`	Sherali-Adams Integrality Gaps Matching the Log-Density Threshold. APPROX-RANDOM Eden Chlamtác, Pasin Manurangsi
2018	J	`jnl`	Sherali-Adams Integrality Gaps Matching the Log-Density Threshold. CoRR Eden Chlamtác, Pasin Manurangsi
2018	J	`jnl`	The Computational Complexity of Training ReLU(s). CoRR Pasin Manurangsi, Daniel Reichman
2018	J	`jnl`	When Do Envy-Free Allocations Exist? CoRR Pasin Manurangsi, Warut Suksompong
2017	A*	`conf`	A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. ICALP Pasin Manurangsi, Prasad Raghavendra
2017	A*	`conf`	Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. STOC Pasin Manurangsi
2017	B	`conf`	An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut. IPCO Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
2017	A*	`conf`	Approximation Algorithms for Label Cover and The Log-Density Threshold. SODA Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan
2017	J	`jnl`	Asymptotic Existence of Fair Divisions for Groups. CoRR Pasin Manurangsi, Warut Suksompong
2017	J	`jnl`	Asymptotic existence of fair divisions for groups. Math. Soc. Sci. Pasin Manurangsi, Warut Suksompong
2017	A*	`conf`	Computing an Approximately Optimal Agreeable Set of Items. IJCAI Pasin Manurangsi, Warut Suksompong
2017	J	`jnl`	Computing an Approximately Optimal Agreeable Set of Items. CoRR Pasin Manurangsi, Warut Suksompong
2017	J	`jnl`	Even 1 × J. Inf. Process. Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, Anak Yodpinyanee
2017	J	`jnl`	Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard. CoRR Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Pasin Manurangsi, Anak Yodpinyanee
2017	A*	`conf`	From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017	J	`jnl`	From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. CoRR Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017	J	`jnl`	Improved Approximation Algorithms for Projection Games. Algorithmica Pasin Manurangsi, Dana Moshkovitz
2017	J	`jnl`	Inapproximability of Maximum Biclique Problems, Minimum $k$-Cut and Densest At-Least-$k$-Subgraph from the Small Set Expansion Hypothesis. CoRR Pasin Manurangsi
2017	A*	`conf`	Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis. ICALP Pasin Manurangsi
2017	A*	`conf`	Inapproximability of VC Dimension and Littlestone's Dimension. COLT Pasin Manurangsi, Aviad Rubinstein
2017	J	`jnl`	Inapproximability of VC Dimension and Littlestone's Dimension. CoRR Pasin Manurangsi, Aviad Rubinstein
2017	J	`jnl`	On the Parameterized Complexity of Approximating Dominating Set. CoRR Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2017	J	`jnl`	On the Parameterized Complexity of Approximating Dominating Set. Electron. Colloquium Comput. Complex. Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi
2017	J	`jnl`	Parameterized Approximation Algorithms for Directed Steiner Network Problems. CoRR Rajesh Chitnis, Andreas Emil Feldmann, Pasin Manurangsi
2016	J	`jnl`	A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. CoRR Pasin Manurangsi, Prasad Raghavendra
2016	J	`jnl`	Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph. CoRR Pasin Manurangsi
2016	J	`jnl`	Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph. Electron. Colloquium Comput. Complex. Pasin Manurangsi
2016	J	`jnl`	An Improved Integrality Gap for the Calinescu-Karloff-Rabani Relaxation for Multiway Cut. CoRR Haris Angelidakis, Yury Makarychev, Pasin Manurangsi
2016	—	`conf`	Near-Optimal UGC-hardness of Approximating Max k-CSP_R. APPROX-RANDOM Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
2015	—	`conf`	Approximating Dense Max 2-CSPs. APPROX-RANDOM Pasin Manurangsi, Dana Moshkovitz
2015	J	`jnl`	Approximating Dense Max 2-CSPs. CoRR Pasin Manurangsi, Dana Moshkovitz
2015	—	`conf`	Dissection with the Fewest Pieces is Hard, Even to Approximate. JCDCGG Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, Anak Yodpinyanee
2015	J	`jnl`	Dissection with the Fewest Pieces is Hard, Even to Approximate. CoRR Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, Anak Yodpinyanee
2015	J	`jnl`	Near-Optimal UGC-hardness of Approximating Max k-CSP_R. CoRR Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
2014	J	`jnl`	Improved Approximation Algorithms for Projection Games. CoRR Pasin Manurangsi, Dana Moshkovitz
2013	A	`conf`	Improved Approximation Algorithms for Projection Games - (Extended Abstract). ESA Pasin Manurangsi, Dana Moshkovitz