Variants of Kannan's Theorem are given where the circuits of
the original theorem are replaced by arbitrary recursively presentable
classes of languages that use advice strings and satisfy certain mild
conditions. These variants imply that $\DTIME(n^{k'})^{\NE}/n^k$
does not contain $\PTIME^{\NE}$, $\DTIME(2^{n^{k'}})/n^k$ does
not contain $\EXP$, $\SPACE(n^{k'})/n^k$ does not ... more >>>

Following Feige, we consider the problem of
estimating the average degree of a graph.
Using ``neighbor queries'' as well as ``degree queries'',
we show that the average degree can be approximated
arbitrarily well in sublinear time, unless the graph is extremely sparse
(e.g., unless the graph has a sublinear ... more >>>

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.
For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ... more >>>