2009 |
74 | EE | Pascal Koiran,
Sylvain Perifel:
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent
CoRR abs/0902.1866: (2009) |
73 | EE | Irénée Briquel,
Pascal Koiran:
Toward a Dichotomy Theorem for Polynomial Evaluation
CoRR abs/0902.2300: (2009) |
2008 |
72 | EE | Erich Kaltofen,
Pascal Koiran:
Expressing a fraction of two determinants as a determinant.
ISSAC 2008: 141-146 |
71 | EE | Pascal Koiran,
Klaus Meer:
On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width.
WG 2008: 252-263 |
70 | EE | Pascal Koiran,
Jürgen Landes,
Natacha Portier,
Penghui Yao:
Adversary Lower Bounds for Nonadaptive Quantum Algorithms.
WoLLIC 2008: 226-237 |
69 | EE | Pascal Koiran,
Jürgen Landes,
Natacha Portier,
Penghui Yao:
Adversary lower bounds for nonadaptive quantum algorithms
CoRR abs/0804.1440: (2008) |
68 | EE | Pierre Charbit,
Emmanuel Jeandel,
Pascal Koiran,
Sylvain Perifel,
Stéphan Thomassé:
Finding a vector orthogonal to roughly half a collection of vectors.
J. Complexity 24(1): 39-53 (2008) |
2007 |
67 | EE | Uffe Flarup,
Pascal Koiran,
Laurent Lyaudet:
On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices.
ISAAC 2007: 124-136 |
66 | EE | Pascal Koiran:
Decision Versus Evaluation in Algebraic Complexity.
MCU 2007: 80-89 |
65 | EE | Pascal Koiran,
Sylvain Perifel:
VPSPACE and a Transfer Theorem over the Complex Field.
MFCS 2007: 359-370 |
64 | EE | Pascal Koiran,
Sylvain Perifel:
VPSPACE and a Transfer Theorem over the Reals.
STACS 2007: 417-428 |
63 | EE | Laurent Lyaudet,
Pascal Koiran,
Uffe Flarup:
On the expressive power of planar perfect matching and permanents of bounded treewidth matrices
CoRR abs/0705.3751: (2007) |
62 | EE | Pascal Koiran,
Sylvain Perifel:
VPSPACE and a transfer theorem over the complex field
CoRR abs/0706.1477: (2007) |
61 | EE | Pascal Koiran,
Sylvain Perifel:
Interpolation in Valiant's theory
CoRR abs/0710.0360: (2007) |
60 | EE | Pascal Koiran,
Vincent Nesme,
Natacha Portier:
The quantum query complexity of the abelian hidden subgroup problem.
Theor. Comput. Sci. 380(1-2): 115-126 (2007) |
59 | EE | Pascal Koiran,
Sylvain Perifel:
The complexity of two problems on arithmetic circuits.
Theor. Comput. Sci. 389(1-2): 172-181 (2007) |
2006 |
58 | EE | Erich Kaltofen,
Pascal Koiran:
Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields.
ISSAC 2006: 162-168 |
57 | EE | Pascal Koiran,
Sylvain Perifel:
Valiant's Model: From Exponential Sums to Exponential Products.
MFCS 2006: 596-607 |
56 | EE | Pascal Koiran,
Sylvain Perifel:
VPSPACE and a Transfer Theorem over the Reals
CoRR abs/cs/0610009: (2006) |
2005 |
55 | EE | Pascal Koiran,
Vincent Nesme,
Natacha Portier:
A Quantum Lower Bound for the Query Complexity of Simon's Problem.
ICALP 2005: 1287-1298 |
54 | EE | Erich Kaltofen,
Pascal Koiran:
On the complexity of factoring bivariate supersparse (Lacunary) polynomials.
ISSAC 2005: 208-215 |
53 | EE | Pascal Koiran,
Vincent Nesme,
Natacha Portier:
A quantum lower bound for the query complexity of Simon's problem
CoRR abs/quant-ph/0501060: (2005) |
52 | EE | Pascal Koiran:
Valiant's model and the cost of computing integers.
Computational Complexity 13(3-4): 131-146 (2005) |
51 | EE | Askold Khovanskii,
Pascal Koiran,
Teresa Krick,
Gregorio Malajovich,
Joseph F. Traub:
Guest editors' preface.
J. Complexity 21(1): 4- (2005) |
50 | EE | Harm Derksen,
Emmanuel Jeandel,
Pascal Koiran:
Quantum automata and algebraic groups.
J. Symb. Comput. 39(3-4): 357-371 (2005) |
49 | EE | Vincent D. Blondel,
Emmanuel Jeandel,
Pascal Koiran,
Natacha Portier:
Decidable and Undecidable Problems about Quantum Automata.
SIAM J. Comput. 34(6): 1464-1473 (2005) |
2004 |
48 | EE | Pascal Koiran:
Valiant's model and the cost of computing integers
Electronic Colloquium on Computational Complexity (ECCC)(003): (2004) |
2003 |
47 | EE | Alexander L. Chistov,
Hervé Fournier,
Leonid Gurvits,
Pascal Koiran:
Vandermonde Matrices, NP-Completeness, and Transversal Subspaces.
Foundations of Computational Mathematics 3(4): 421-427 (2003) |
46 | | Pascal Koiran:
The theory of Liouville functions.
J. Symb. Log. 68(2): 353-365 (2003) |
2002 |
45 | EE | Pascal Koiran:
Transfer theorems via sign conditions.
Inf. Process. Lett. 81(2): 65-69 (2002) |
44 | | Olivier Chapuis,
Ehud Hrushovski,
Pascal Koiran,
Bruno Poizat:
La Limite des Theories de Courbes Generiques.
J. Symb. Log. 67(1): 24-34 (2002) |
2001 |
43 | | Pascal Koiran,
Natacha Portier:
Back-and-forth systems for generic curves and a decision algorithm for the limit theory.
Ann. Pure Appl. Logic 111(3): 257-275 (2001) |
42 | EE | Pascal Koiran:
The topological entropy of iterated piecewise affine maps is uncomputable.
Discrete Mathematics & Theoretical Computer Science 4(2): 351-356 (2001) |
41 | | Vincent D. Blondel,
Olivier Bournez,
Pascal Koiran,
John N. Tsitsiklis:
The Stability of Saturated Linear Dynamical Systems Is Undecidable.
J. Comput. Syst. Sci. 62(3): 442-462 (2001) |
40 | EE | Vincent D. Blondel,
Olivier Bournez,
Pascal Koiran,
Christos H. Papadimitriou,
John N. Tsitsiklis:
Deciding stability and mortality of piecewise affine dynamical systems.
Theor. Comput. Sci. 255(1-2): 687-696 (2001) |
2000 |
39 | EE | Hervé Fournier,
Pascal Koiran:
Lower Bounds Are Not Easier over the Reals: Inside PH.
ICALP 2000: 832-843 |
38 | EE | Pascal Koiran:
Circuits versus Trees in Algebraic Complexity.
STACS 2000: 35-52 |
37 | EE | Vincent D. Blondel,
Olivier Bournez,
Pascal Koiran,
John N. Tsitsiklis:
The Stability of Saturated Linear Dynamical Systems Is Undecidable.
STACS 2000: 479-490 |
36 | EE | Pascal Koiran:
The Complexity of Local Dimensions for Constructible Sets.
J. Complexity 16(1): 311-323 (2000) |
35 | EE | Jean-Pierre Dedieu,
Pascal Koiran:
Guest Editors' Preface.
J. Complexity 16(3): 528 (2000) |
1999 |
34 | | Olivier Chapuis,
Pascal Koiran:
Saturation and Stability in the Theory of Computation over the Reals.
Ann. Pure Appl. Logic 99(1-3): 1-49 (1999) |
33 | EE | Pascal Koiran:
The Real Dimension Problem Is NPR-Complete.
J. Complexity 15(2): 227-238 (1999) |
32 | | Felipe Cucker,
Pascal Koiran,
Steve Smale:
A Polynomial Time Algorithm for Diophantine Equations in One Variable.
J. Symb. Comput. 27(1): 21-29 (1999) |
31 | | Olivier Chapuis,
Pascal Koiran:
Definability of Geometric Properties on Algebraically Closed Fields.
Math. Log. Q. 45: 533-550 (1999) |
30 | EE | Pascal Koiran,
Cristopher Moore:
Closed-for Analytic Maps in One and Two Dimensions can Simulate Universal Turing Machines.
Theor. Comput. Sci. 210(1): 217-223 (1999) |
29 | EE | Pascal Koiran:
Elimination of Parameters in the Polynomial Hierarchy.
Theor. Comput. Sci. 215(1-2): 289-304 (1999) |
1998 |
28 | EE | Hervé Fournier,
Pascal Koiran:
Are Lower Bounds Easier over the Reals?
STOC 1998: 507-513 |
27 | EE | Pascal Koiran,
Eduardo D. Sontag:
Vapnik-Chervonenkis Dimension of Recurrent Neural Networks.
Discrete Applied Mathematics 86(1): 63-79 (1998) |
1997 |
26 | | Pascal Koiran,
Eduardo D. Sontag:
Vapnik-Chervonenkis Dimension of Recurrent Neural Networks.
EuroCOLT 1997: 223-237 |
25 | EE | Pascal Koiran:
Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties.
FOCS 1997: 36-45 |
24 | EE | Felipe Cucker,
Pascal Koiran,
Martín Matamala:
Complexity and Dimension.
Inf. Process. Lett. 62(4): 209-212 (1997) |
23 | EE | Pascal Koiran:
Elimination of Constants from Machines over Algebraically Closed Fields.
J. Complexity 13(1): 65-82 (1997) |
22 | | Pascal Koiran:
A Weak Version of the Blum, Shub, and Smale Model.
J. Comput. Syst. Sci. 54(1): 177-189 (1997) |
21 | | Pascal Koiran,
Eduardo D. Sontag:
Neural Networks with Quadratic VC Dimension.
J. Comput. Syst. Sci. 54(1): 190-198 (1997) |
20 | | Leonid Gurvits,
Pascal Koiran:
Approximation and Learning of Convex Superpositions.
J. Comput. Syst. Sci. 55(1): 161-170 (1997) |
1996 |
19 | EE | Pascal Koiran:
VC Dimension in Circuit Complexity.
IEEE Conference on Computational Complexity 1996: 81-85 |
18 | EE | Pascal Koiran:
Hilbert's Nullstellensatz Is in the Polynomial Hierarchy.
J. Complexity 12(4): 273-286 (1996) |
17 | EE | Pascal Koiran:
A Family of Universal Recurrent Networks.
Theor. Comput. Sci. 168(2): 473-480 (1996) |
1995 |
16 | | Leonid Gurvits,
Pascal Koiran:
Approximation and learning of convex superpositions.
EuroCOLT 1995: 222-236 |
15 | | Pascal Koiran:
Approximating the Volume of Definable Sets.
FOCS 1995: 134-141 |
14 | EE | Pascal Koiran,
Eduardo D. Sontag:
Neural Networks with Quadratic VC Dimension.
NIPS 1995: 197-203 |
13 | EE | Felipe Cucker,
Marek Karpinski,
Pascal Koiran,
Thomas Lickteig,
Kai Werther:
On real Turing machines that toss coins.
STOC 1995: 335-342 |
12 | EE | Pascal Koiran:
VC Dimension in Circuit Complexity
Electronic Colloquium on Computational Complexity (ECCC) 2(51): (1995) |
11 | EE | Felipe Cucker,
Pascal Koiran:
Computing over the Reals with Addition and Order: Higher Complexity Classes.
J. Complexity 11(3): 358-376 (1995) |
1994 |
10 | EE | Pascal Koiran:
Efficient Learning of Continuous Neural Networks.
COLT 1994: 348-355 |
9 | EE | Michel Cosnard,
Pascal Koiran,
Hélène Paugam-Moisy:
Bounds on the Number of Units for Computing Arbitrary Dichotomies by Multilayer Perceptrons.
J. Complexity 10(1): 57-63 (1994) |
8 | | Pascal Koiran,
Michel Cosnard,
Max H. Garzon:
Computability with Low-Dimensional Dynamical Systems.
Theor. Comput. Sci. 132(2): 113-128 (1994) |
7 | | Pascal Koiran:
Computing over the Reals with Addition and Order.
Theor. Comput. Sci. 133(1): 35-47 (1994) |
1993 |
6 | | Pascal Koiran:
A Weak Version of the Blum, Shub & Smale model
FOCS 1993: 486-495 |
5 | | Michel Cosnard,
Max H. Garzon,
Pascal Koiran:
Computability Properties of Low-dimensional Dynamical Systems.
STACS 1993: 365-373 |
4 | EE | Pascal Koiran:
On the complexity of approximating mappings using feedforward networks.
Neural Networks 6(5): 649-653 (1993) |
1992 |
3 | | Michel Cosnard,
Pascal Koiran:
Relations between Models of Parallel Abstract Machines.
Heinz Nixdorf Symposium 1992: 37-46 |
2 | | Michel Cosnard,
Pascal Koiran,
Hélène Paugam-Moisy:
Complexity Issues in Neural Network Computations.
LATIN 1992: 530-543 |
1991 |
1 | | Jacques Cohen,
Pascal Koiran,
Catherine Perrin:
Meta-Level Interpretation of CLP(Lists).
WCLP 1991: 457-481 |