Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > UPPER BOUNDS:
Reports tagged with upper bounds:
TR95-010 | 16th February 1995
Pavel Pudlak, Jiri Sgall

#### An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

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 >>>

TR96-045 | 28th August 1996
Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe

#### Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems

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 >>>

TR98-045 | 17th July 1998
Detlef Sieling

#### A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs

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 >>>

TR02-013 | 30th January 2002
Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

#### Quantum and Stochastic Programs of Bounded Width

Revisions: 1

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 >>>

TR05-030 | 12th February 2005
Evgeny Dantsin, Alexander Wolpert

#### An Improved Upper Bound for SAT

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 >>>

TR13-042 | 25th March 2013
Siu Man Chan

#### Just a Pebble Game

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 >>>

ISSN 1433-8092 | Imprint