Pavel Pudlak, Jiri Sgall

We prove an unexpected upper bound on a communication game proposed

by Jeff Edmonds and Russell Impagliazzo as an approach for

proving lower bounds for time-space tradeoffs for branching programs.

Our result is based on a generalization of a construction of Erdos,

Frankl and Rodl of a large 3-hypergraph ...
more >>>

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe

We study EP, the subclass of NP consisting of those

languages accepted by NP machines that when they accept always have a

number of accepting paths that is a power of two. We show that the

negation equivalence problem for OBDDs (ordered binary decision

diagrams) ...
more >>>

Detlef Sieling

For (1,+k)-branching programs and read-k-times branching

programs syntactic and nonsyntactic variants can be distinguished. The

nonsyntactic variants correspond in a natural way to sequential

computations with restrictions on reading the input while lower bound

proofs are easier or only known for the syntactic variants. In this

paper it is shown ...
more >>>

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

We prove upper and lower bounds on the power of quantum and stochastic

branching programs of bounded width. We show any NC^1 language can

be accepted exactly by a width-2 quantum branching program of

polynomial length, in contrast to the classical case where width 5 is

necessary unless \NC^1=\ACC. ...
more >>>

Evgeny Dantsin, Alexander Wolpert

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most $2^{n(1-1/\alpha)}$ up to a polynomial factor, where $\alpha = \ln(m/n) + O(\ln \ln m)$ and $n$, $m$ are respectively the number of variables ... more >>>

Siu Man Chan

The two-player pebble game of Dymond–Tompa is identified as a barrier for existing techniques to save space or to speed up parallel algorithms for evaluation problems.

Many combinatorial lower bounds to study L versus NL and NC versus P under different restricted settings scale in the same way as the ... more >>>