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

TR03-034 | 17th March 2003
Arnold Beckmann

Height restricted constant depth LK

Height restricted constant depth LK is a natural restriction of
Gentzen's propositional proof system LK. A sequence of LK-formulas
has polylogarithmic-height restricted depth-d-LK proofs iff the
n-th formula in the sequence possesses LK-proofs where cut-formulas
are of depth d+1 with small bottom fanin
and of ... more >>>


TR03-033 | 6th May 2003
Meir Feder, Dana Ron, Ami Tavory

Bounds on Linear Codes for Network Multicast

Comments: 1

Traditionally, communication networks are composed of
routing nodes, which relay and duplicate data. Work in
recent years has shown that for the case of multicast, an
improvement in both rate and code-construction complexity can be
gained by replacing these routing nodes by linear coding
nodes. These nodes transmit linear combinations ... more >>>


TR03-032 | 16th April 2003
Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

Approximating Longest Directed Path

We investigate the hardness of approximating the longest path and
the longest cycle in directed graphs on $n$ vertices. We show that
neither of these two problems can be polynomial time approximated
within $n^{1-\epsilon}$ for any $\epsilon>0$ unless
$\text{P}=\text{NP}$. In particular, the result holds for
more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint