Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with projection reductions:
TR95-017 | 27th March 1995
Claudia Bertram, Thomas Hofmeister

Multiple Product Modulo Arbitrary Numbers

We consider the threshold circuit complexity of computing
the multiple product modulo m in threshold circuits.

more >>>

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

TR95-048 | 5th October 1995
Helmut Veith

Succinct Representation and Leaf Languages

In this paper, we present stronger results in the theory of succinct
problem representation by boolean circuits, and establish a close
relationship between succinct problems and leaf languages. As
a major tool, we use quantifierfree projection reductions
from descriptive complexity theory.

In particular, we show that the succinct upgrading ... more >>>

ISSN 1433-8092 | Imprint