The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose ... more >>>

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial f computed by a constant-depth circuit over rational numbers, and outputs a list L of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of f computable by constant-depth circuits. This ... more >>>

Analyzing refutations of the well known
pebbling formulas we prove some new strong connections between pebble games and algebraic proof system, showing that
there is a parallelism between the reversible, black and black-white pebbling games on one side, and
the three algebraic proof systems NS, MC and ... more >>>