7 citations · 10 across the 7 of their papers we have counts for
4 papers · 1 filter
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent
Pascal Koiran, Sylvain Perifel
We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.
Adversary lower bounds for nonadaptive quantum algorithms
Pacal Koiran, Jürgen Landes, Natacha Portier +1
We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.
Interpolation in Valiant's theory
Pascal Koiran, Sylvain Perifel
We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit…
VPSPACE and a Transfer Theorem over the Reals
Pascal Koiran, Sylvain Perifel
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our ma…