Joshua Brakensiek

Manik Dhar

IEEE Trans. Inf. Theory, October, 2024

Robust Factorizations and Colorings of Tensor Graphs.

[BibT_eX]

[DOI]

Sami Davies

SIAM J. Discret. Math., March, 2024

Redundancy Is All You Need.

[BibT_eX]

[DOI]

CoRR, 2024

Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes.

[BibT_eX]

[DOI]

CoRR, 2024

AG Codes Achieve List Decoding Capacity over Constant-Sized Fields.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Generalized GM-MDS: Polynomial Codes Are Higher Order MDS.

[BibT_eX]

[DOI]

Manik Dhar

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Tight approximability of MAX 2-SAT and relatives, under UGC.

[BibT_eX]

[DOI]

Neng Huang

Uri Zwick

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

2023

AG codes achieve list decoding capacity over contant-sized fields.

[BibT_eX]

[DOI]

CoRR, 2023

SDPs and Robust Satisfiability of Promise CSP.

[BibT_eX]

[DOI]

Sai Sandeep

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Generic Reed-Solomon Codes Achieve List-Decoding Capacity.

[BibT_eX]

[DOI]

Visu Makam

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Separating MAX 2-AND, MAX DI-CUT and MAX CUT.

[BibT_eX]

[DOI]

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

2022

Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes.

[BibT_eX]

[DOI]

Visu Makam

IEEE Trans. Inf. Theory, 2022

Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

The Resolution of Keller's Conjecture.

[BibT_eX]

[DOI]

J. Autom. Reason., 2022

2021

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Conditional Dichotomy of Boolean Ordered Promise CSPs.

[BibT_eX]

[DOI]

Sai Sandeep

Electron. Colloquium Comput. Complex., 2021

Lower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes.

[BibT_eX]

[DOI]

Visu Makam

CoRR, 2021

2020

The Resolution of Keller's Conjecture - Computation Logs.

[BibT_eX]

[DOI]

Dataset, April, 2020

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

A Simple Sublinear Algorithm for Gap Edit Distance.

[BibT_eX]

[DOI]

Moses Charikar

Aviad Rubinstein

CoRR, 2020

Constant-factor approximation of near-linear edit distance in near-linear time.

[BibT_eX]

[DOI]

Aviad Rubinstein

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

Symmetric Polymorphisms and Efficient Decidability of Promise CSPs.

[BibT_eX]

[DOI]

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

Coded trace reconstruction in a constant number of traces.

[BibT_eX]

[DOI]

Ray Li

Bruce Spang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Smoothed Complexity of 2-player Nash Equilibria.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Bridging between 0/1 and Linear Programming via Random Walks.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

The Resolution of Keller's Conjecture.

[BibT_eX]

[DOI]

Marijn Heule

John Mackey

CoRR, 2019

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs.

[BibT_eX]

[DOI]

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

2018

Combining LPs and Ring Equations via Structured Polymorphisms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy.

[BibT_eX]

[DOI]

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

2017

A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

The Quest for Strong Inapproximability Results with Perfect Completeness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

New hardness results for graph and hypergraph colorings.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

Efficient Low-Redundancy Codes for Correcting Multiple Deletions.

[BibT_eX]

[DOI]

Samuel Zbarsky

Electron. Colloquium Comput. Complex., 2015

2013

Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees

[BibT_eX]

[DOI]