A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems

Julia Chuzhoy; Mina Dalirrooyfard; Vadim Grinberg; Zihan Tan

doi:10.4230/LIPIcs.ITCS.2023.38

A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems

Julia Chuzhoy
, Mina Dalirrooyfard
, Vadim Grinberg
, Zihan Tan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

We propose a new conjecture on hardness of 2-CSP's, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a variation of the Graph Crossing Number problem, follow from this conjecture. The conjecture can be viewed as occupying a middle ground between the d-to-1 conjecture, and hardness results for 2-CSP's that can be obtained via standard techniques, such as Parallel Repetition combined with standard 2-prover protocols for the 3SAT problem. We hope that this work will motivate further exploration of hardness of 2-CSP's in the regimes arising from the conjecture. We believe that a positive resolution of the conjecture will provide a good starting point for other hardness of approximation proofs. Another contribution of our work is proving that the problems that we consider are roughly equivalent from the approximation perspective. Some of these problems arose in previous work, from which it appeared that they may be related to each other. We formalize this relationship in this work.

Original language	English (US)
Title of host publication	14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Editors	Yael Tauman Kalai
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959772631
DOIs	https://doi.org/10.4230/LIPIcs.ITCS.2023.38
State	Published - Jan 1 2023
Externally published	Yes
Event	14th Innovations in Theoretical Computer Science Conference, ITCS 2023 - Cambridge, United States Duration: Jan 10 2023 → Jan 13 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	251
ISSN (Print)	1868-8969

Conference

Conference	14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Country/Territory	United States
City	Cambridge
Period	1/10/23 → 1/13/23

Bibliographical note

Publisher Copyright:
© Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, and Zihan Tan; licensed under Creative Commons License CC-BY 4.0.

Keywords

Densest k-Subgraph
Hardness of Approximation

Publisher link

10.4230/LIPIcs.ITCS.2023.38

Find It

Find It at U of M Libraries

Cite this

Chuzhoy, J., Dalirrooyfard, M., Grinberg, V., & Tan, Z. (2023). A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems. In Y. T. Kalai (Ed.), 14th Innovations in Theoretical Computer Science Conference, ITCS 2023 Article 38 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 251). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2023.38

A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems. / Chuzhoy, Julia; Dalirrooyfard, Mina; Grinberg, Vadim et al.
14th Innovations in Theoretical Computer Science Conference, ITCS 2023. ed. / Yael Tauman Kalai. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 38 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 251).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chuzhoy, J, Dalirrooyfard, M, Grinberg, V & Tan, Z 2023, A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems. in YT Kalai (ed.), 14th Innovations in Theoretical Computer Science Conference, ITCS 2023., 38, Leibniz International Proceedings in Informatics, LIPIcs, vol. 251, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, Cambridge, United States, 1/10/23. https://doi.org/10.4230/LIPIcs.ITCS.2023.38

Chuzhoy J, Dalirrooyfard M, Grinberg V, Tan Z. A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems. In Kalai YT, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 38. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ITCS.2023.38

Chuzhoy, Julia ; Dalirrooyfard, Mina ; Grinberg, Vadim et al. / A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems. 14th Innovations in Theoretical Computer Science Conference, ITCS 2023. editor / Yael Tauman Kalai. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{1292bcee8ea54e1d80b06912322cc8a9,

title = "A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems",

abstract = "We propose a new conjecture on hardness of 2-CSP's, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a variation of the Graph Crossing Number problem, follow from this conjecture. The conjecture can be viewed as occupying a middle ground between the d-to-1 conjecture, and hardness results for 2-CSP's that can be obtained via standard techniques, such as Parallel Repetition combined with standard 2-prover protocols for the 3SAT problem. We hope that this work will motivate further exploration of hardness of 2-CSP's in the regimes arising from the conjecture. We believe that a positive resolution of the conjecture will provide a good starting point for other hardness of approximation proofs. Another contribution of our work is proving that the problems that we consider are roughly equivalent from the approximation perspective. Some of these problems arose in previous work, from which it appeared that they may be related to each other. We formalize this relationship in this work.",

keywords = "Densest k-Subgraph, Hardness of Approximation",

author = "Julia Chuzhoy and Mina Dalirrooyfard and Vadim Grinberg and Zihan Tan",

note = "Publisher Copyright: {\textcopyright} Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, and Zihan Tan; licensed under Creative Commons License CC-BY 4.0.; 14th Innovations in Theoretical Computer Science Conference, ITCS 2023 ; Conference date: 10-01-2023 Through 13-01-2023",

year = "2023",

month = jan,

day = "1",

doi = "10.4230/LIPIcs.ITCS.2023.38",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Kalai, \{Yael Tauman\}",

booktitle = "14th Innovations in Theoretical Computer Science Conference, ITCS 2023",

}

TY - GEN

T1 - A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems

AU - Chuzhoy, Julia

AU - Dalirrooyfard, Mina

AU - Grinberg, Vadim

AU - Tan, Zihan

N1 - Publisher Copyright: © Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, and Zihan Tan; licensed under Creative Commons License CC-BY 4.0.

PY - 2023/1/1

Y1 - 2023/1/1

N2 - We propose a new conjecture on hardness of 2-CSP's, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a variation of the Graph Crossing Number problem, follow from this conjecture. The conjecture can be viewed as occupying a middle ground between the d-to-1 conjecture, and hardness results for 2-CSP's that can be obtained via standard techniques, such as Parallel Repetition combined with standard 2-prover protocols for the 3SAT problem. We hope that this work will motivate further exploration of hardness of 2-CSP's in the regimes arising from the conjecture. We believe that a positive resolution of the conjecture will provide a good starting point for other hardness of approximation proofs. Another contribution of our work is proving that the problems that we consider are roughly equivalent from the approximation perspective. Some of these problems arose in previous work, from which it appeared that they may be related to each other. We formalize this relationship in this work.

AB - We propose a new conjecture on hardness of 2-CSP's, and show that new hardness of approximation results for Densest k-Subgraph and several other problems, including a graph partitioning problem, and a variation of the Graph Crossing Number problem, follow from this conjecture. The conjecture can be viewed as occupying a middle ground between the d-to-1 conjecture, and hardness results for 2-CSP's that can be obtained via standard techniques, such as Parallel Repetition combined with standard 2-prover protocols for the 3SAT problem. We hope that this work will motivate further exploration of hardness of 2-CSP's in the regimes arising from the conjecture. We believe that a positive resolution of the conjecture will provide a good starting point for other hardness of approximation proofs. Another contribution of our work is proving that the problems that we consider are roughly equivalent from the approximation perspective. Some of these problems arose in previous work, from which it appeared that they may be related to each other. We formalize this relationship in this work.

KW - Densest k-Subgraph

KW - Hardness of Approximation

UR - https://www.scopus.com/pages/publications/85147544648

UR - https://www.scopus.com/pages/publications/85147544648#tab=citedBy

U2 - 10.4230/LIPIcs.ITCS.2023.38

DO - 10.4230/LIPIcs.ITCS.2023.38

M3 - Conference contribution

AN - SCOPUS:85147544648

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023

A2 - Kalai, Yael Tauman

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023

Y2 - 10 January 2023 through 13 January 2023

ER -

A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems

Abstract

Publication series

Conference

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this