Zobrazeno 1 - 10
of 10
pro vyhledávání: '"Susanna F. de Rezende"'
Autor:
Susanna F. de Rezende
Publikováno v:
Procedia Computer Science. 195:152-162
Autor:
Susanna F. de Rezende, Ilario Bonacina, Jakob Nordström, Massimo Lauria, Albert Atserias, Alexander A. Razborov
Publikováno v:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Scopus-Elsevier
Recercat. Dipósit de la Recerca de Catalunya
instname
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
STOC
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-STOC 2018
Universitat Politècnica de Catalunya (UPC)
Scopus-Elsevier
Recercat. Dipósit de la Recerca de Catalunya
instname
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
STOC
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-STOC 2018
We prove that for k ≪ 4√n regular resolution requires length nΩ(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4358b5424aed31f07e64de86ce6bc749
http://arxiv.org/abs/2012.09476
http://arxiv.org/abs/2012.09476
Publikováno v:
FOCS
University of Copenhagen
University of Copenhagen
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to a
Autor:
Robert Robere, Toniann Pitassi, Marc Vinyals, Susanna F. de Rezende, Jakob Nordström, Or Meir
Publikováno v:
FOCS
University of Copenhagen
University of Copenhagen
We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality
Publikováno v:
de Rezende, S F, Nordstrom, J, Meir, O & Robere, R 2019, Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling . in 34th Computational Complexity Conference (CCC 2019), Proceedings . vol. 137, 18, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Leibniz International Proceedings in Informatics, LIPIcs, vol. 137, pp. 1-16, 34th Computational Complexity Conference, CCC 2019, New Brunswick, United States, 18/07/2019 . https://doi.org/10.4230/LIPIcs.CCC.2019.18
We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::25121cfdbd058d1dca9ece185cf4688e
Publikováno v:
FOCS
We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constantsize coefficients, and the lower bounds apply to length and formula space (i.e., num
Publikováno v:
Electronic Notes in Discrete Mathematics. 38:743-748
In 1966, Gallai asked whether every connected graph has a vertex that is common to all its longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs. Another related question was raised in 199
Publikováno v:
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2015, 566, pp.59-75. ⟨10.1016/j.tcs.2014.11.037⟩
9th International colloquium on graph theory and combinatorics
9th International colloquium on graph theory and combinatorics, Jun 2014, Grenoble, France
[Research Report] RR-8492, INRIA. 2014, pp.23
Theoretical Computer Science, 2015, 566, pp.59-75. ⟨10.1016/j.tcs.2014.11.037⟩
Theoretical Computer Science, Elsevier, 2015, 566, pp.59-75. ⟨10.1016/j.tcs.2014.11.037⟩
9th International colloquium on graph theory and combinatorics
9th International colloquium on graph theory and combinatorics, Jun 2014, Grenoble, France
[Research Report] RR-8492, INRIA. 2014, pp.23
Theoretical Computer Science, 2015, 566, pp.59-75. ⟨10.1016/j.tcs.2014.11.037⟩
An {\it orientation} of a graph~$G$ is a digraph~$D$ obtained from~$G$ by replacing each edge by exactly one of the two possible arcs with the same endvertices. For each~$v \in V(G)$, the \emph{indegree} of~$v$ in~$D$, denoted by~$d^-_D(v)$, is the n
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d8b5b1768f996ebf2634ac300c2da853
https://hal.archives-ouvertes.fr/hal-01101578
https://hal.archives-ouvertes.fr/hal-01101578
Publikováno v:
Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual)
Universidade de São Paulo (USP)
instacron:USP
Universidade de São Paulo (USP)
instacron:USP
In 1966, Gallai asked whether every connected graph has a vertex that is common to all longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs and 2-trees. Another related question was raise
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6ec0e9e4870f7b9ebefaec19e7e0664c
Autor:
Toniann Pitassi, Susanna F. de Rezende, Jakob Nordström, Mika Göös, Dmitry Sokolov, Robert Robere
Publikováno v:
University of Copenhagen
STOC
STOC
We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali–Adams proof systems in time polynomial in the size of the shortest
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4e5651c61891d6054050fe22d0d3f093
https://curis.ku.dk/portal/en/publications/automating-algebraic-proof-systems-is-nphard(706a9771-b323-491a-9204-b914bb4e775c).html
https://curis.ku.dk/portal/en/publications/automating-algebraic-proof-systems-is-nphard(706a9771-b323-491a-9204-b914bb4e775c).html