Pasin Manurangsi

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

Differentially Private Heatmaps.

[BibT_eX]

[DOI]

Nachiappan Valliappan

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Consensus Halving for Sets of Items.

[BibT_eX]

[DOI]

Math. Oper. Res., November, 2022

Near-Optimal NP-Hardness of Approximating Max k-CSPR.

[BibT_eX]

[DOI]

Preetum Nakkiran

Theory Comput., 2022

Almost envy-freeness for groups: Improved bounds via discrepancy theory.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Private Aggregation of Trajectories.

[BibT_eX]

[DOI]

Proc. Priv. Enhancing Technol., 2022

Multiparty Reach and Frequency Histogram: Private, Secure, and Practical.

[BibT_eX]

[DOI]

Proc. Priv. Enhancing Technol., 2022

Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions.

[BibT_eX]

[DOI]

Proc. Priv. Enhancing Technol., 2022

Distributed, Private, Sparse Histograms in the Two-Server Model.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2022

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds.

[BibT_eX]

[DOI]

CoRR, 2022

Generalized kings and single-elimination winners in random tournaments.

[BibT_eX]

[DOI]

Auton. Agents Multi Agent Syst., 2022

Tight Bounds for Differentially Private Anonymized Histograms.

[BibT_eX]

[DOI]

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Private Isotonic Regression.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Anonymized Histograms in Intermediate Privacy Models.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Cryptographic Hardness of Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Faster Privacy Accounting via Evolving Discretization.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Large-Scale Differentially Private BERT.

[BibT_eX]

[DOI]

Proceedings of the Findings of the Association for Computational Linguistics: EMNLP 2022, 2022

Private Robust Estimation by Stabilizing Convex Relaxations.

[BibT_eX]

[DOI]

Pravesh Kothari

Ameya Velingker

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Hardness of Learning a Single Neuron with Adversarial Label Noise.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

The Price of Justified Representation.

[BibT_eX]

[DOI]

Ulrike Schmidt-Kraepelin

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

Private Rank Aggregation in Central and Local Models.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Parameterized Approximation Algorithms for Bidirected Steiner Network Problems.

[BibT_eX]

[DOI]

Rajesh Chitnis

Andreas Emil Feldmann

ACM Trans. Algorithms, 2021

Closing Gaps in Asymptotic Fair Division.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

On the complexity of fair house allocation.

[BibT_eX]

[DOI]

Naoyuki Kamiyama

Oper. Res. Lett., 2021

The Price of Fairness for Indivisible Goods.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2021

Parameterized Intractability of Even Set and Shortest Vector Problem.

[BibT_eX]

[DOI]

J. ACM, 2021

Linear discrepancy is Π2-hard to approximate.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2021

User-Level Private Learning via Correlated Sampling.

[BibT_eX]

[DOI]

CoRR, 2021

Google COVID-19 Vaccination Search Insights: Anonymization Process Description.

[BibT_eX]

[DOI]

CoRR, 2021

Approximation and hardness of Shift-Bribery.

[BibT_eX]

[DOI]

Piotr Faliszewski

Krzysztof Sornat

Artif. Intell., 2021

Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems.

[BibT_eX]

[DOI]

Szymon Dudycz

Jan Marcinkowski

Proceedings of the Approximation and Online Algorithms - 19th International Workshop, 2021

Sample-efficient proper PAC learning with approximate differential privacy.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

User-Level Differentially Private Learning via Correlated Sampling.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Deep Learning with Label Differential Privacy.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

The Strongish Planted Clique Hypothesis and Its Consequences.

[BibT_eX]

[DOI]

Aviad Rubinstein

Tselil Schramm

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Algorithmic Persuasion with Evidence.

[BibT_eX]

[DOI]

Martin Hoefer

Alexandros Psomas

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Tight Hardness Results for Training Depth-2 ReLU Networks.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

On Distributed Differential Privacy and Counting Distinct Elements.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Locally Private k-Means in One Round.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Near-tight closure b ounds for the Littlestone and threshold dimensions.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2021

Robust and Private Learning of Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

When Do Envy-Free Allocations Exist?

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Multitasking Capacity: Hardness Results and Improved Constructions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms.

[BibT_eX]

[DOI]

Andreas Emil Feldmann

Karthik C. S.

Euiwoong Lee

Electron. Colloquium Comput. Complex., 2020

Near-tight closure bounds for Littlestone and threshold dimensions.

[BibT_eX]

[DOI]

CoRR, 2020

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic.

[BibT_eX]

[DOI]

Karthik C. S.

Comb., 2020

To Close Is Easier Than To Open: Dual Parameterization To k-Median.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms - 18th International Workshop, 2020

Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem).

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Differentially Private Clustering: Tight Approximation Ratios.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise.

[BibT_eX]

[DOI]

Ilias Diakonikolas

Daniel M. Kane

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Tight Approximation for Proportional Approval Voting.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Pure Differentially Private Summation from Anonymous Messages.

[BibT_eX]

[DOI]

Proceedings of the 1st Conference on Information-Theoretic Cryptography, 2020

Private Aggregation from Fewer Anonymous Messages.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - EUROCRYPT 2020, 2020

2019

Approximation and Hardness: Beyond P and NP.

[BibT_eX]

[DOI]

PhD thesis, 2019

On the Parameterized Complexity of Approximating Dominating Set.

[BibT_eX]

[DOI]

Karthik C. S.

Bundit Laekhanukit

J. ACM, 2019

A note on degree vs gap of Min-Rep Label Cover and improved inapproximability for connectivity problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2019

Nearly Optimal Robust Secret Sharing against Rushing Adversaries.

[BibT_eX]

[DOI]

Prashant Nalini Vasudevan

Akshayaram Srinivasan

IACR Cryptol. ePrint Arch., 2019

Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem).

[BibT_eX]

[DOI]

CoRR, 2019

Computing a small agreeable set of indivisible items.

[BibT_eX]

[DOI]

Artif. Intell., 2019

A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

Losing Treewidth by Separating Subsets.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin.

[BibT_eX]

[DOI]

Ilias Diakonikolas

Daniel Kane

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network.

[BibT_eX]

[DOI]

Irit Dinur

Electron. Colloquium Comput. Complex., 2018

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

The Computational Complexity of Training ReLU(s).

[BibT_eX]

[DOI]

Daniel Reichman

CoRR, 2018

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems.

[BibT_eX]

[DOI]

CoRR, 2018

Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis.

[BibT_eX]

[DOI]

Algorithms, 2018

Average Whenever You Meet: Opportunistic Protocols for Community Detection.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

Sherali-Adams Integrality Gaps Matching the Log-Density Threshold.

[BibT_eX]

[DOI]

Eden Chlamtác

Proceedings of the Approximation, 2018

2017

Asymptotic existence of fair divisions for groups.

[BibT_eX]

[DOI]

Math. Soc. Sci., 2017

Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard.

[BibT_eX]

[DOI]

J. Inf. Process., 2017

Inapproximability of Maximum Biclique Problems, Minimum $k$-Cut and Densest At-Least-$k$-Subgraph from the Small Set Expansion Hypothesis.

[BibT_eX]

[DOI]

CoRR, 2017

Parameterized Approximation Algorithms for Directed Steiner Network Problems.

[BibT_eX]

[DOI]

Rajesh Chitnis

Andreas Emil Feldmann

CoRR, 2017

Even 1×n Edge-Matching and Jigsaw Puzzles are Really Hard.

[BibT_eX]

[DOI]

CoRR, 2017

Improved Approximation Algorithms for Projection Games.

[BibT_eX]

[DOI]

Algorithmica, 2017

Approximation Algorithms for Label Cover and The Log-Density Threshold.

[BibT_eX]

[DOI]

Eden Chlamtác

Aravindan Vijayaraghavan

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

An Improved Integrality Gap for the Călinescu-Karloff-Rabani Relaxation for Multiway Cut.

[BibT_eX]

[DOI]

Haris Angelidakis

Yury Makarychev

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Computing an Approximately Optimal Agreeable Set of Items.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017

A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs.

[BibT_eX]

[DOI]

Prasad Raghavendra

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Inapproximability of VC Dimension and Littlestone's Dimension.

[BibT_eX]

[DOI]

Aviad Rubinstein

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Near-Optimal UGC-hardness of Approximating Max k-CSP_R.

[BibT_eX]

[DOI]

Preetum Nakkiran

Proceedings of the Approximation, 2016

2015

Dissection with the Fewest Pieces is Hard, Even to Approximate.

[BibT_eX]

[DOI]

Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

Approximating Dense Max 2-CSPs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2013

Improved Approximation Algorithms for Projection Games - (Extended Abstract).

[BibT_eX]

[DOI]