We consider satisfiable Tseitin formulas TSG,c based on d-regular expanders G with the absolute value of the second largest eigenvalue less than d3 . We prove that any nondeterministic read-once branching program (1-NBP) representing TSG,c has size 2(n), where n is the number of vertices in G. It extends the recent result by Itsykson at el. [9] from OBDD to 1-NBP. On the other hand it is easy to see that TSG,c can be represented as a read-2 branching program (2-BP) of size O(n), as the negation of a nondeterministic read-once branching program (1-coNBP) of size O(n) and as a CNF formula of size O(n). Thus TSG,c gives the best possible separations (up to a constant in the exponent) between 1-NBP and 2-BP, 1-NBP and 1-coNBP and between 1-NBP and CNF.

Original languageEnglish
Title of host publication42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
EditorsKim G. Larsen, Jean-Francois Raskin, Hans L. Bodlaender
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770460
DOIs
StatePublished - 1 Nov 2017
Event42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 - Aalborg, Denmark
Duration: 21 Aug 201725 Aug 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume83
ISSN (Print)1868-8969

Conference

Conference42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
Country/TerritoryDenmark
CityAalborg
Period21/08/1725/08/17

    Research areas

  • Expander, Read-once branching program, Tseitin formula

    Scopus subject areas

  • Software

ID: 49785281