Zobrazeno 1 - 6
of 6
pro vyhledávání: '"Risse, Kilian"'
We prove that Sherali-Adams with polynomially bounded coefficients requires proofs of size $n^{\Omega(d)}$ to rule out the existence of an $n^{\Theta(1)}$-clique in Erd\H{o}s-R\'{e}nyi random graphs whose maximum clique is of size $d\leq 2\log n$. Th
Externí odkaz:
http://arxiv.org/abs/2404.16722
Autor:
Austrin, Per, Risse, Kilian
We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$, SoS requires degree $\Omega(s^{1-\epsilon})$ to prove t
Externí odkaz:
http://arxiv.org/abs/2311.12994
Autor:
Håstad, Johan, Risse, Kilian
We study Frege proofs using depth-$d$ Boolean formulas for the Tseitin contradiction on $n \times n$ grids. We prove that if each line in the proof is of size $M$ then the number of lines is exponential in $n/(\log M)^{O(d)}$. This strengthens a rece
Externí odkaz:
http://arxiv.org/abs/2209.05839
Autor:
Austrin, Per, Risse, Kilian
Publikováno v:
TheoretiCS, Volume 1 (December 21, 2022) theoretics:9012
We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requir
Externí odkaz:
http://arxiv.org/abs/2201.10835
We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the reg
Externí odkaz:
http://arxiv.org/abs/1912.00534
Publikováno v:
de Rezende, S F, Nordström, J, Risse, K & Sokolov, D 2020, Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs . in S Saraf (ed.), 35th Computational Complexity Conference, CCC 2020 ., 28, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, vol. 169, pp. 1-24, 35th Computational Complexity Conference, CCC 2020, Virtual, Online, Germany, 28/07/2020 . https://doi.org/10.4230/LIPIcs.CCC.2020.28
We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the reg
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8e9347cf3432646e6c8588438f152a83