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

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

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