Standard

(Semi)Algebraic proofs over {±1} variables. / Sokolov, Dmitry.

STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. ред. / Konstantin Makarychev; Yury Makarychev; Madhur Tulsiani; Gautam Kamath; Julia Chuzhoy. Association for Computing Machinery, 2020. стр. 78-90 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование

Harvard

Sokolov, D 2020, (Semi)Algebraic proofs over {±1} variables. в K Makarychev, Y Makarychev, M Tulsiani, G Kamath & J Chuzhoy (ред.), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, стр. 78-90, 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, Соединенные Штаты Америки, 22/06/20. https://doi.org/10.1145/3357713.3384288

APA

Sokolov, D. (2020). (Semi)Algebraic proofs over {±1} variables. в K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Ред.), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (стр. 78-90). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3357713.3384288

Vancouver

Sokolov D. (Semi)Algebraic proofs over {±1} variables. в Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, Редакторы, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2020. стр. 78-90. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/3357713.3384288

Author

Sokolov, Dmitry. / (Semi)Algebraic proofs over {±1} variables. STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Редактор / Konstantin Makarychev ; Yury Makarychev ; Madhur Tulsiani ; Gautam Kamath ; Julia Chuzhoy. Association for Computing Machinery, 2020. стр. 78-90 (Proceedings of the Annual ACM Symposium on Theory of Computing).

BibTeX

@inproceedings{a162522664154841a76c1b82b240af66,
title = "(Semi)Algebraic proofs over {±1} variables",
abstract = "One of the major open problems in proof complexity is to prove lower bounds on AC0[p]-Frege proof systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove lower bounds on the size for Polynomial Calculus over the {± 1} basis. In this paper we show a technique for proving such lower bounds and moreover we also give lower bounds on the size for Sum-of-Squares over the {± 1} basis. We show lower bounds on random {"}-CNF formulas and formulas composed with a gadget. As a byproduct, we establish a separation between Polynomial Calculus and Sum-of-Squares over the {± 1} basis by proving a lower bound on the Pigeonhole Principle.",
keywords = "Lower bounds, Polynomial calculus, Proof complexity, Random formulas, Sum-of-squares",
author = "Dmitry Sokolov",
note = "Funding Information: ∗This work was done while at Lund University and the University of Copenhagen supported by the Knut and Alice Wallenberg grant KAW 2016.0433. Publisher Copyright: {\textcopyright} 2020 ACM. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 ; Conference date: 22-06-2020 Through 26-06-2020",
year = "2020",
month = jun,
day = "8",
doi = "10.1145/3357713.3384288",
language = "English",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "78--90",
editor = "Konstantin Makarychev and Yury Makarychev and Madhur Tulsiani and Gautam Kamath and Julia Chuzhoy",
booktitle = "STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing",
address = "United States",

}

RIS

TY - GEN

T1 - (Semi)Algebraic proofs over {±1} variables

AU - Sokolov, Dmitry

N1 - Funding Information: ∗This work was done while at Lund University and the University of Copenhagen supported by the Knut and Alice Wallenberg grant KAW 2016.0433. Publisher Copyright: © 2020 ACM. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/6/8

Y1 - 2020/6/8

N2 - One of the major open problems in proof complexity is to prove lower bounds on AC0[p]-Frege proof systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove lower bounds on the size for Polynomial Calculus over the {± 1} basis. In this paper we show a technique for proving such lower bounds and moreover we also give lower bounds on the size for Sum-of-Squares over the {± 1} basis. We show lower bounds on random "-CNF formulas and formulas composed with a gadget. As a byproduct, we establish a separation between Polynomial Calculus and Sum-of-Squares over the {± 1} basis by proving a lower bound on the Pigeonhole Principle.

AB - One of the major open problems in proof complexity is to prove lower bounds on AC0[p]-Frege proof systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove lower bounds on the size for Polynomial Calculus over the {± 1} basis. In this paper we show a technique for proving such lower bounds and moreover we also give lower bounds on the size for Sum-of-Squares over the {± 1} basis. We show lower bounds on random "-CNF formulas and formulas composed with a gadget. As a byproduct, we establish a separation between Polynomial Calculus and Sum-of-Squares over the {± 1} basis by proving a lower bound on the Pigeonhole Principle.

KW - Lower bounds

KW - Polynomial calculus

KW - Proof complexity

KW - Random formulas

KW - Sum-of-squares

UR - http://www.scopus.com/inward/record.url?scp=85086759464&partnerID=8YFLogxK

U2 - 10.1145/3357713.3384288

DO - 10.1145/3357713.3384288

M3 - Conference contribution

AN - SCOPUS:85086759464

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 78

EP - 90

BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Makarychev, Konstantin

A2 - Makarychev, Yury

A2 - Tulsiani, Madhur

A2 - Kamath, Gautam

A2 - Chuzhoy, Julia

PB - Association for Computing Machinery

T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020

Y2 - 22 June 2020 through 26 June 2020

ER -

ID: 75310263