Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

Comments: 2

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