Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with time complexity:
TR06-111 | 18th July 2006
Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Revisions: 2

We present two new methods for finding a lowest common ancestor (LCA)
for each pair of vertices of a directed acyclic graph (dag) on
n vertices and m edges.

The first method is a natural approach that solves the all-pairs LCA
problem for the input dag in time O(nm).

The ... more >>>

TR06-115 | 26th July 2006
Artur Czumaj, Andrzej Lingas

Finding a Heaviest Triangle is not Harder than Matrix Multiplication

We show that for any $\epsilon > 0$, a maximum-weight triangle in an
undirected graph with $n$ vertices and real weights assigned to
vertices can be found in time $\O(n^{\omega} + n^{2 + \epsilon})$,
where $\omega $ is the exponent of fastest matrix multiplication
algorithm. By the currently best bound ... more >>>

TR08-076 | 17th June 2008
Ryan Williams

Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

ISSN 1433-8092 | Imprint