Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with GAP:
TR95-034 | 30th June 1995
Christoph Meinel, Stephan Waack

Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems

We investigate the probabilistic communication complexity
(more exactly, the majority communication complexity,)
of the graph accessibility problem GAP and
its counting versions MOD_k-GAP, k > 1.
Due to arguments concerning matrix variation ranks
and certain projection reductions, we prove
that, for any partition of the input variables,
more >>>

TR98-026 | 5th May 1998
Richard Beigel

Gaps in Bounded Query Hierarchies

Prior results show that most bounded query hierarchies cannot
contain finite gaps. For example, it is known that
P<sub>(<i>m</i>+1)-tt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup> implies P<sub>btt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup>
and for all sets <i>A</i>
<li> FP<sub>(<i>m</i>+1)-tt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies FP<sub>btt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>
<li> P<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies P<sub>bT</sub><sup><i>A</i></sup> = ... more >>>

TR09-025 | 11th March 2009
Arnaldo Moura, Igor Carboni Oliveira

A New Look at Some Classical Results in Computational Complexity

We propose a generalization of the traditional algorithmic space and
time complexities. Using the concept introduced, we derive an
unified proof for the deterministic time and space hierarchy
theorems, now stated in a much more general setting. This opens the
possibility for the unification and generalization of other results
that ... more >>>

ISSN 1433-8092 | Imprint