We prove a quasi-polynomial lower bound on the size of bounded-depth
Frege proofs of the pigeonhole principle $PHP^{m}_n$ where
$m= (1+1/{\polylog n})n$.
This lower bound qualitatively matches the known quasi-polynomial-size
bounded-depth Frege proofs for these principles.
Our technique, which uses a switching lemma argument like other lower bounds
for ... more >>>

Understanding the structure of real-time neural computation in
highly recurrent neural microcircuits that consist of complex
heterogeneous components has remained a serious challenge for
computational modeling. We propose here a new conceptual framework
that strongly differs from all previous approaches based on
computational models inspired ... more >>>

The subclass of directed series-parallel graphs plays an important role in
computer science. Whether a given graph is series-parallel is a
well studied problem in algorithmic graph theory, for which fast sequential and
parallel algorithms have been developed in a sequence of papers.
Also methods are known to solve ... more >>>