Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR00-008 | 20th January 2000
Albert Atserias, Nicola Galesi, Ricard Gavaldà

Monotone Proofs of the Pigeon Hole Principle

We study the complexity of proving the Pigeon Hole
Principle (PHP) in a monotone variant of the Gentzen Calculus, also
known as Geometric Logic. We show that the standard encoding
of the PHP as a monotone sequent admits quasipolynomial-size proofs
in this system. This result is a consequence of ... more >>>


TR00-007 | 14th December 1999
Pavlos S. Efraimidis, Paul Spirakis

Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines


The problem of Scheduling $n$ Independent Jobs
on $m$ Unrelated Parallel Machines, when $m$
is fixed, is considered. The standard problem
of minimizing the makespan of the schedule
(SUM) and the bicriteria problem of scheduling
with bounded makespan and cost (SUMC), are
addressed, and randomized fully linear time
more >>>


TR00-006 | 26th January 2000
E.A. Okol'nishnikiva

On operations of geometrical projection and monotone extension


Some operations over Boolean functions are considered. It is shown that
the operation of the geometrical projection and the operation of the
monotone extension can increase the complexity of Boolean functions for
formulas in each finite basis, for switching networks, for branching
programs, and read-$k$-times ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint