Zobrazeno 1 - 10
of 32
pro vyhledávání: '"Dmitry Itsykson"'
Publikováno v:
ACM Transactions on Computational Logic. 22:1-30
This article is motivated by seeking lower bounds on OBDD(∧, w, r) refutations, namely, OBDD refutations that allow weakening and arbitrary reorderings. We first work with 1 - NBP ∧ refutations based on read-once nondeterministic branching progra
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d3406175cdb55fc4db831856e953c5b0
https://doi.org/10.1145/3468855
https://doi.org/10.1145/3468855
Autor:
Ludmila Glinskih, Dmitry Itsykson
Publikováno v:
Theory of Computing Systems. 65:613-633
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5bc4ee0fc20b120a5840a3f867f443a5
https://doi.org/10.1007/s00224-020-10007-8
https://doi.org/10.1007/s00224-020-10007-8
Publikováno v:
computational complexity. 30
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1dea260dc8a778ba5e2f6de6d3c7aa5f
https://doi.org/10.1007/s00037-021-00216-z
https://doi.org/10.1007/s00037-021-00216-z
Publikováno v:
computational complexity. 30
This paper is motivated by seeking the exact complexity of resolution refutation of Tseitin formulas. We prove that the size of any regular resolution refutation of a Tseitin formula $$ {\rm T}(G, c)$$ based on a connected graph $${G} =(V, E)$$ is at
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3c990479dfd8de841fb10ed5111d6f3b
https://doi.org/10.1007/s00037-021-00213-2
https://doi.org/10.1007/s00037-021-00213-2
We prove that there is a constant K such that Tseitin formulas for an undirected graph G requires proofs of size 2^{tw(G)^{Omega(1/d)}} in depth-d Frege systems for d
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4b7885776f3f5db8db66e3e8ee058ced
http://hdl.handle.net/11573/1311217
http://hdl.handle.net/11573/1311217
Autor:
Dmitry Itsykson, Ludmila Glinskih
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783030199548
CSR
CSR
We show that any nondeterministic read-once branching program that decides a satisfiable Tseitin formula based on an \(n\times n\) grid graph has size at least \(2^{\varOmega (n)}\). Then using the Excluded Grid Theorem by Robertson and Seymour we sh
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::410c1ce6ea5ea49881a5a366b01aad0f
https://doi.org/10.1007/978-3-030-19955-5_13
https://doi.org/10.1007/978-3-030-19955-5_13
Publikováno v:
Fundamenta Informaticae. 145:229-242
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7de52434c8cf397064f4a55a2ab1ca43
https://doi.org/10.3233/fi-2016-1358
https://doi.org/10.3233/fi-2016-1358
Autor:
Dmitry Itsykson, Dmitry Sokolov
Publikováno v:
Annals of Pure and Applied Logic. 171:102722
We consider an extension of the resolution proof system that operates with disjunctions of linear equalities over F 2 ; we denote this system by Res(⊕). It is well known that tree-like resolution is equivalent in behavior to DPLL algorithms for the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::438fc371b3b749bcf9977b97122c7e43
https://doi.org/10.1016/j.apal.2019.102722
https://doi.org/10.1016/j.apal.2019.102722
Autor:
Dmitry Itsykson, Alexander Knop
Publikováno v:
Theory and Applications of Satisfiability Testing – SAT 2017 ISBN: 9783319662626
SAT
SAT
Itsykson and Sokolov in 2014 introduced the class of \(\mathrm {DPLL}(\oplus )\) algorithms that solve Boolean satisfiability problem using the splitting by linear combinations of variables modulo 2. This class extends the class of \(\mathrm {DPLL}\)
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b8a9c2d1362a410af1aa9de0cab945e7
https://doi.org/10.1007/978-3-319-66263-3_4
https://doi.org/10.1007/978-3-319-66263-3_4
Publikováno v:
34th Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. pp.43:1-43:14, ⟨10.4230/LIPIcs.STACS.2017.43⟩
The Journal of Symbolic Logic
The Journal of Symbolic Logic, Association for Symbolic Logic, In press, pp.1-41. ⟨10.1017/jsl.2019.53⟩
The Journal of Symbolic Logic, Association for Symbolic Logic, 2020, 85 (2), pp.632-670. ⟨10.1017/jsl.2019.53⟩
STACS: Symposium on Theoretical Aspects of Computer Science
STACS: Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. pp.43:1-43:14, ⟨10.4230/LIPIcs.STACS.2017.43⟩
The Journal of Symbolic Logic
The Journal of Symbolic Logic, Association for Symbolic Logic, In press, pp.1-41. ⟨10.1017/jsl.2019.53⟩
The Journal of Symbolic Logic, Association for Symbolic Logic, 2020, 85 (2), pp.632-670. ⟨10.1017/jsl.2019.53⟩
In 2004 Atserias, Kolaitis, and Vardi proposed $\text {OBDD}$ -based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false $\text {OBDD}$ from $\text {OBDD}$ s representing clauses of the initia
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1f5e331c039ddd67ab31b064932551e3