| No. |
Title |
Author |
Year |
| 1 |
Algorithms with More Granular Differential Privacy Guarantees |
Ghazi, Badih et al. |
2023 |
| 2 |
Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique |
Manurangsi, Pasin |
2023 |
| 3 |
Private Counting of Distinct and k-Occurring Items in Time Windows |
Ghazi, Badih et al. |
2023 |
| 4 |
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems |
Abboud, Amir et al. |
2022 |
| 5 |
Algorithmic Persuasion with Evidence |
Hoefer, Martin et al. |
2021 |
| 6 |
On Distributed Differential Privacy and Counting Distinct Elements |
Chen, Lijie et al. |
2021 |
| 7 |
The Strongish Planted Clique Hypothesis and Its Consequences |
Manurangsi, Pasin et al. |
2021 |
| 8 |
Tight Hardness Results for Training Depth-2 ReLU Networks |
Goel, Surbhi et al. |
2021 |
| 9 |
Pure Differentially Private Summation from Anonymous Messages |
Ghazi, Badih et al. |
2020 |
| 10 |
A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation |
Manurangsi, Pasin |
2018 |
| 11 |
Average Whenever You Meet: Opportunistic Protocols for Community Detection |
Becchetti, Luca et al. |
2018 |
| 12 |
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network |
Dinur, Irit et al. |
2018 |
| 13 |
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut |
Manurangsi, Pasin et al. |
2018 |
| 14 |
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic |
C. S., Karthik et al. |
2018 |
| 15 |
Parameterized Approximation Algorithms for Bidirected Steiner Network Problems |
Chitnis, Rajesh et al. |
2018 |
| 16 |
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH |
Bhattacharyya, Arnab et al. |
2018 |
| 17 |
Sherali-Adams Integrality Gaps Matching the Log-Density Threshold |
Chlamtác, Eden et al. |
2018 |
| 18 |
A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs |
Manurangsi, Pasin et al. |
2017 |
| 19 |
Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis |
Manurangsi, Pasin |
2017 |
| 20 |
Near-Optimal UGC-hardness of Approximating Max k-CSP_R |
Manurangsi, Pasin et al. |
2016 |
| 21 |
Approximating Dense Max 2-CSPs |
Manurangsi, Pasin et al. |
2015 |
