Euiwoong Lee

Thatchaphol Saranurak

CoRR, 2024

Max-Cut with ε-Accurate Predictions.

[BibT_eX]

[DOI]

CoRR, 2024

Separating k-Median from the Supplier Version.

[BibT_eX]

[DOI]

Aditya Anand

CoRR, 2024

A PTAS for ℓ0-Low Rank Approximation: Solving Dense CSPs over Reals.

[BibT_eX]

[DOI]

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

Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs.

[BibT_eX]

[DOI]

Pasin Manurangsi

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Strong hardness of approximation for tree transversals.

[BibT_eX]

[DOI]

Pengxiang Wang

Inf. Process. Lett., March, 2023

Inapproximability of Matrix p → q Norms.

[BibT_eX]

[DOI]

SIAM J. Comput., February, 2023

A PTAS for 𝓁0-Low Rank Approximation: Solving Dense CSPs over Reals.

[BibT_eX]

[DOI]

CoRR, 2023

On the Fine-Grained Complexity of Approximating k-Center in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A Local Search-Based Approach for Set Covering.

[BibT_eX]

[DOI]

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median.

[BibT_eX]

[DOI]

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

On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs.

[BibT_eX]

[DOI]

Suprovat Ghoshal

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

On some variants of Euclidean k-supplier.

[BibT_eX]

[DOI]

Viswanath Nagarajan

Lily Wang

Oper. Res. Lett., 2022

Optimal Bounds for the k-cut Problem.

[BibT_eX]

[DOI]

J. ACM, 2022

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median.

[BibT_eX]

[DOI]

CoRR, 2022

Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion.

[BibT_eX]

[DOI]

Jungho Ahn

Eun Jung Kim

Algorithmica, 2022

A characterization of approximability for biased CSPs.

[BibT_eX]

[DOI]

Suprovat Ghoshal

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics.

[BibT_eX]

[DOI]

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

Matroid-Based TSP Rounding for Half-Integral Solutions.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem.

[BibT_eX]

[DOI]

Vijay Bhattiprolu

Madhur Tulsiani

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 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

Correlation Clustering with Sherali-Adams.

[BibT_eX]

[DOI]

Alantha Newman

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Fitting Metrics and Ultrametrics with Minimum Disagreements.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams.

[BibT_eX]

[DOI]

ACM Trans. Knowl. Discov. Data, 2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in $\ell_p$-metrics.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics.

[BibT_eX]

[DOI]

CoRR, 2021

A framework for quadratic form maximization over convex sets through nonconvex relaxations.

[BibT_eX]

[DOI]

Vijay Bhattiprolu

Assaf Naor

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

The Connectivity Threshold for Dense Graphs.

[BibT_eX]

[DOI]

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

On Approximability of Clustering Problems Without Candidate Centers.

[BibT_eX]

[DOI]

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

A Constant-Factor Approximation for Weighted Bond Cover.

[BibT_eX]

[DOI]

Eun Jung Kim

Dimitrios M. Thilikos

Proceedings of the Approximation, 2021

2020

Maximum Matching in the Online Batch-arrival Model.

[BibT_eX]

[DOI]

Sahil Singla

ACM Trans. Algorithms, 2020

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

[BibT_eX]

[DOI]

Andreas Emil Feldmann

Pasin Manurangsi

Electron. Colloquium Comput. Complex., 2020

Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering.

[BibT_eX]

[DOI]

Vaggos Chatziafratis

Neha Gupta

CoRR, 2020

Optimal Bounds for the k-cut Problem.

[BibT_eX]

[DOI]

CoRR, 2020

The Karger-Stein algorithm is optimal for k-cut.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection.

[BibT_eX]

[DOI]

Vaggos Chatziafratis

Grigory Yaroslavtsev

Konstantin Makarychev

Sara Ahmadian

Alessandro Epasto

Mohammad Mahdian

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Partitioning a graph into small pieces with applications to path transversal.

[BibT_eX]

[DOI]

Karthekeyan Chandrasekaran

Math. Program., 2019

Beating the 2-approximation factor for global bicut.

[BibT_eX]

[DOI]

Kristóf Bérczi

Tamás Király

Chao Xu

Math. Program., 2019

Improved 3LIN Hardness via Linear Label Cover.

[BibT_eX]

[DOI]

Prahladh Harsha

Subhash Khot

Devanathan Thiruvenkatachari

Electron. Colloquium Comput. Complex., 2019

The Number of Minimum k-Cuts: Improving the Karger-Stein Bound.

[BibT_eX]

[DOI]

CoRR, 2019

The number of minimum k-cuts: improving the Karger-Stein bound.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Losing Treewidth by Separating Subsets.

[BibT_eX]

[DOI]

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

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness.

[BibT_eX]

[DOI]

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

A PTAS for ℓp-Low Rank Approximation.

[BibT_eX]

[DOI]

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

Tight FPT Approximations for k-Median and k-Means.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes.

[BibT_eX]

[DOI]

Badih Ghazi

IEEE Trans. Inf. Theory, 2018

Approximating Operator Norms via Generalized Krivine Rounding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Inapproximability of Matrix p→q Norms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

A PTAS for 𝓁p-Low Rank Approximation.

[BibT_eX]

[DOI]

CoRR, 2018

DiSLR: Distributed Sampling with Limited Redundancy For Triangle Counting in Graph Streams.

[BibT_eX]

[DOI]

CoRR, 2018

Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs.

[BibT_eX]

[DOI]

Comb., 2018

An FPT Algorithm Beating 2-Approximation for k-Cut.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tri-Fly: Distributed Estimation of Global and Local Triangle Counts in Graph Streams.

[BibT_eX]

[DOI]

Proceedings of the Advances in Knowledge Discovery and Data Mining, 2018

Faster Exact and Approximate Algorithms for k-Cut.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities.

[BibT_eX]

[DOI]

Sahil Singla

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

2017

Towards a Characterization of Approximation Resistance for Symmetric CSPs.

[BibT_eX]

[DOI]

Theory Comput., 2017

Inapproximability of H-Transversal/Packing.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

Improved and simplified inapproximability for k-means.

[BibT_eX]

[DOI]

Melanie Schmidt

John Wright

Inf. Process. Lett., 2017

APX-hardness of maximizing Nash social welfare with indivisible items.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2017

An FPT Algorithm Beating 2-Approximation for k-Cut.

[BibT_eX]

[DOI]

CoRR, 2017

Minimum Birkhoff-von Neumann Decomposition.

[BibT_eX]

[DOI]

Janardhan Kulkarni

Mohit Singh

Proceedings of the Integer Programming and Combinatorial Optimization, 2017

Why You Should Charge Your Friends for Borrowing Your Stuff.

[BibT_eX]

[DOI]

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

Improved Hardness for Cut, Interdiction, and Firefighter Problems.

[BibT_eX]

[DOI]

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

Understanding the Correlation Gap For Matchings.

[BibT_eX]

[DOI]

Guru Guruganesh

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere.

[BibT_eX]

[DOI]

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

Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere.

[BibT_eX]

[DOI]

Vijay Bhattiprolu

Karthekeyan Chandrasekaran

Proceedings of the Approximation, 2017

Global and Fixed-Terminal Cuts in Digraphs.

[BibT_eX]

[DOI]

Kristóf Bérczi

Tamás Király

Chao Xu

Proceedings of the Approximation, 2017

2016

Simple Proof of Hardness of Feedback Vertex Set.

[BibT_eX]

[DOI]

Vijay V. S. P. Bhattiprolu

Theory Comput., 2016

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy.

[BibT_eX]

[DOI]

Vijay V. S. P. Bhattiprolu

CoRR, 2016

2015

Nearly Optimal NP-Hardness of Unique Coverage.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Hardness of Graph Pricing Through Generalized Max-Dicut.

[BibT_eX]

[DOI]

Vijay V. S. P. Bhattiprolu

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate Hypergraph Coloring under Low-discrepancy and Related Promises.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Inapproximability of Feedback Vertex Set for Bounded Length Cycles.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Complexity of approximating CSP with Balance / Hard Constraints.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Clustering Affine Subspaces: Hardness and Algorithms.

[BibT_eX]

[DOI]

Leonard J. Schulman

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Improved bounds on the price of stability in network cost sharing games.

[BibT_eX]

[DOI]