[Recent Theses] [Recent Papers and Preprints] [Books] [Journal Publications] [Refereed Contributions] [Nonrefereed Contributions]

Recent Theses

• S. Mengel
  Conjunctive Queries, Arithmetic Circuits and Counting Complexity
  Dissertation, Universität Paderborn (2013)
  pdf
• C. Ikenmeyer
  Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients
  Dissertation, Universität Paderborn (2012)
  pdf
• D. Amelunxen
  Geometric analysis of the condition of the convex feasibility problem
  Dissertation, Universität Paderborn (2011)
  pdf

• S. Mengel
  Arithmetic Branching Programs with Memory
  accepted for the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2013
  arXiv 1303.1969
  Abstract pdf
• F. Capelli, A. Durand, S. Mengel
  The arithmetic complexity of tensor contractions
  Proceedings Symposium on Theoretical Aspects of Computer Science (STACS) 2013
  arXiv 1209.4865
  Abstract conference version
• A. Durand, S. Mengel
  Structural Tractability of Counting of Solutions to Conjunctive Queries
  Proceeding of the 16th International Conference on Database Theory (ICDT 2013)
  arXiv 1303.2059
  Abstract pdf conference version
• A. Durand, S. Mengel
  The Complexity of Weighted Counting for Acyclic Conjunctive Queries
  submitted
  accepted for the Journal of Computer and System Sciences (JCSS)
  arXiv 1110.4201
  Abstract pdf
• P. Bürgisser and C. Ikenmeyer
  Explicit Lower Bounds via Geometric Complexity Theory
  arXiv 1210.8368
  Accepted for the 45th ACM Symposium on Theory of Computing 2013 Abstract  pdf 

• C. Ikenmeyer
  Small Littlewood-Richardson coefficients
  arXiv 1209.1521
  Abstract  ps  pdf 
  [ Java Applet ]

• D. Amelunxen and P. Bürgisser
  Intrinsic volumes of symmetric cones
  arXiv 1205.1863
  Abstract  pdf 
  

• P. Bürgisser and C. Ikenmeyer
  Deciding Positivity of Littlewood-Richardson coefficients
  arXiv 1204.2484
  Abstract  pdf 
  [ Java Applet ]

• H. Fournier, G Malod, S. Mengel
  Monomials in arithmetic circuits: Complete problems in the counting hierarchy
  Proceedings Symposium on Theoretical Aspects of Computer Science (STACS) 2012
  arXiv 1110.6271
  Abstract  pdf  conference version 

• D. Amelunxen and P. Bürgisser
  Probabilistic analysis of the Grassmann condition number
  arXiv 1112.2603
  Abstract  pdf 

• Stefan Mengel
  Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
  Extended abstract in Proc. of ICALP 2011
  Lecture Notes in Computer Science, Volume 6755/2011, p. 700-711, Springer, 2011
  Abstract  ps  pdf 
  Full version
  Abstract  ps  pdf 

• D. Amelunxen and P. Bürgisser
  A coordinate-free condition number for convex programming
  SIAM Journal on Optimization 22(3): 1029-1041 (2012).
  arXiv 1105.4049
  Abstract  pdf 

• P. Bürgisser and C. Ikenmeyer
  Geometric Complexity Theory and Tensor Rank
  Proceedings 43rd Annual ACM Symposium on Theory of Computing 2011, pp. 509 - 518
  arXiv 1011.1350v1
  Abstract  ps  pdf 

• P. Bürgisser, M. Christandl and C. Ikenmeyer
  Even partitions in plethysms
  Journal of Algebra 328: 322-329 (2011).
  arXiv 1003.4474v1
  Abstract  ps  pdf 

• P. Bürgisser
  Smoothed Analysis of Condition Numbers
  Invited Paper in Section 15: Mathematical Aspects of Computer Science
  International Congress of Mathematicians, Hyderabad, India, 2010
  Abstract  pdf 

• P. Bürgisser and F. Cucker
  Smoothed Analysis of Moore-Penrose Inversion
  SIAM J. Matrix Anal. & Appl. 31(5): 2769-2783 (2010).
  Abstract  pdf 

• P. Bürgisser and F. Cucker
  On a Problem Posed by Steve Smale
  Annals of Mathematics 174(3): 1785-1836 (2011).
  arXiv 0909.2114
  Abstract  pdf 

• P. Bürgisser and F. Cucker
  Solving Polynomial Equations in Smoothed Polynomial Time and a Near Solution to Smale's 17th Problem
  In Proceedings STOC 2010, pp. 503-512.
  Abstract  pdf 

• P. Bürgisser, M. Christandl and C. Ikenmeyer
  Nonvanishing of Kronecker coefficients for rectangular shapes
  Advances in Mathematics 227 (2011), pp. 2082 - 2091.
  arXiv 0910.4512
  Abstract  ps  pdf 

• Oberwolfach Report No. 52/2009 on "Complexity Theory"
  organised by Peter Bürgisser, Joachim von zur Gathen, Oded Goldreich, and Madhu Sudan
  Oberwolfach Reports, Vol. 6, Issue 4, pp. 2787 - 2850, 2009
  European Mathematical Society
  Abstract  ps  pdf 

• P. Bürgisser, J.M. Landsberg, L. Manivel, and J. Weyman
  An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP
  SIAM J. Comput. 40(4): 1179-1209 (2011)
  arXiv 0907.2850
  Abstract  ps  pdf 

• P. Bürgisser and C. Ikenmeyer
  A max-flow algorithm for positivity of Littlewood-Richardson coefficients
  FPSAC 2009, Hagenberg, Austria, DMTCS proc. AK, 2009, pp. 267-278
  Abstract  pdf 

• P. Bürgisser
  Smoothed Analysis of Condition Numbers, in
  Foundations of Computational Mathematics, Hong Kong 2008
  (Eds F. Cucker, A. Pinkus, M. Todd), pp. 1- 41. London Mathematical Society Lecture Note Series 363, Cambridge University Press ,2009
  Abstract  pdf

• P. Bürgisser and P. Scheiblechner
  Counting Irreducible Components of Complex Algebraic Varieties
  Computational Complexity 19: 1-35 (2010)
  Abstract  pdf

• P. Bürgisser and D. Amelunxen
  Robust Smoothed Analysis of a Condition Number for Linear Programming
  Mathematical Programming 131(1): 221-251 (2012)
  arXiv 0803.0925
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker, and M. Lotz
  Coverage Processes on Spheres and Condition Numbers for Linear Programming
  The Annals of Probability 38(2): 570-604 (2010)
  Abstract  pdf

• P. Bürgisser and C. Ikenmeyer
  The Complexity of Computing Kronecker Coefficients
  FPSAC 2008, Valparaiso-Viña del Mar, Chile, DMTCS proc. AJ, 2008, pp. 357-368
  Abstract  pdf

• P. Bürgisser
  Average volume, curvatures, and Euler characteristic of random real algebraic varieties
  arXiv math.PR/0606755
  Abstract  ps

	P. Bürgisser, M. Clausen, and M.A. Shokrollahi Algebraic Complexity Theory Grundlehren der mathematischen Wissenschaften, No. 315 Springer Verlag 1997, 618 + xxiii pp. ISBN 3-540-60582-7
	P. Bürgisser, M. Clausen, and M.A. Shokrollahi Algebraic Complexity Theory Sciencep . Reprint authorized by Springer Verlag (Berlin/Heidelberg/New York) for sale in the People's Republic of China, 2007. ISBN 978-7-03-018299-9.
	P. Bürgisser Completeness and Reduction in Algebraic Complexity Theory Algorithms and Computation in Mathematics, No. 7 Springer Verlag 2000, 168 + xii pp. ISBN 3-540-66752-0

	P. Bürgisser, F. Cucker Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré In: Complexity of computations and proofs, Jan Krajicek (ed.), Quaderni di Matematica 13, pp. 73--152, 2005. Abstract  ps  pdf
	P. Bürgisser Lower Bounds and Real Algebraic Geometry In: Algorithmic and Quantitative Real Algebraic Geometry, Saugata Basu, Laureano Gonzalez-Vega (eds.), DIMACS Series, Volume 60, AMS, pp. 35--54, 2003. Abstract  ps  pdf   Erratum: ps  pdf
	P. Bürgisser, A. Kurth, A. Wagner Incorporating Severity Variations into Credit Risk In: Innovations in Risk Management: Seminal Papers from the Journal of Risk P.Jorion (Editor), pp.533--567, Incisive Media Investments Limited, 2004 Abstract   ps   pdf
	P. Bürgisser, M. Clausen, M.A. Shokrollahi Algebraic Complexity Theory In: Handbook of Computer Algebra, J. Grabmeier, E. Kaltofen, and V. Weispfenning (eds.) pp. 125-128, Springer Verlag, 2003.

• P. Bürgisser and P. Scheiblechner
  On the Complexity of Counting Components of Algebraic Varieties
  Journal of Symbolic Computation. 44 (2009), 1114-1136.
  Abstract  ps  pdf

• P. Bürgisser
  On defining integers and proving arithmetic circuit lower bounds
  Computational Complexity 18: 81-103 (2009)
  Preliminary version in Proc. of STACS 2007, 133-144, February 2007, Aachen.
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker
  Exotic quantifiers, complexity classes, and complete problems
  ECCC Report TR05-138
  Foundations of Computational Mathematics 9(2): 135-170 (2009).
  Abstract  ps  pdf

• E. Allender, P. Bürgisser, J. Kjeldgaard-Pedersen, and P. Miltersen
  On the Complexity of Numerical Analysis
  SIAM J. Comput. 38(5): 1987-2006 (2009).
  Abstract  pdf
  Conference version in Proc. of 21st Ann. IEEE Conference on Computational Complexity, pp. 331-339, 2006, Prague.
  pdf

• P. Bürgisser, F. Cucker, and M. Lotz
  The probability that a slightly perturbed numerical analysis problem is difficult
  Math. Comp. 77 (2008), 1559-1583.
  Abstract  ps  pdf
  Warning: unfortunately, due to an error in the production of the paper, binomial coefficients have been replaced by fractions at several places in the journal version! For a correct version see arXiv math/0610270

• P. Bürgisser
  Average Euler Characteristic of Random Real Algebraic Varieties
  Comptes Rendus - Mathematique, vol 345/9, pp. 507-512 (2007)
  Abstract  ps  pdf

• P. Bürgisser and P. Scheiblechner
  Differential Forms in Computational Algebraic Geometry
  Proc. of ISSAC 2007, 61-68, July 29 - August 1, Waterloo, Canada
  Abstract  ps  pdf

• P. Scheiblechner
  On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
  Journal of Complexity 23(3): 359-379 (2007).
  Abstract  ps  pdf

• P. Bürgisser, M. Lotz
  The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties
  Foundations of Computational Mathematics 7(1): 51-86 (2007).
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker, M. Lotz
  General formulas for the smoothed analysis of condition numbers
  C. R. Acad. Sci. Paris, Ser. I 343, pp.145-150 (2006)
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker, and M. Lotz
  Smoothed analysis of complex conic condition numbers
  Journal de Mathématiques Pures et Appliquées 86: 293-309 (2006)
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker, and P. de Naurois
  The complexity of semilinear problems in succinct representation
  Computational Complexity 15(3): 197-235 (2006)
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker
  Counting Complexity Classes for Numeric Computations
  II: Algebraic and Semialgebraic Sets
  Journal of Complexity, 22(2):147-191 (2006)
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker, M. Lotz
  Counting Complexity Classes for Numeric Computations
  III: Complex Projective Sets
  Foundations of Computational Mathematics 5(4):351-387 (2005)
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker, M. Lotz
  The Complexity to Compute the Euler Characteristic of Complex Varieties
  C. R. Acad. Sci. Paris, Ser. I 339, pp.371-376 (2004)
  Abstract  ps  pdf

• P. Bürgisser
  The Complexity of Factors of Multivariate Polynomials
  Foundations of Computational Mathematics 4(4):369-396 (2004).
  Abstract  ps  pdf

• P. Bürgisser, M. Lotz
  Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps
  Journal of the ACM 51(3):464-482 (2004).  
  Abstract  ps  pdf

• M. Lotz, J. A. Makowsky
  On the algebraic complexity of some families of coloured Tutte polynomials
  Advances in Applied Mathematics 32(1-2):327-349 (2004)
  Abstract  ps  pdf

• P. Bürgisser, F. Cucker
  Counting Complexity Classes for Numeric Computations
  I: Semilinear Sets
  SIAM J. Comp. 33(1):227-260 (2003)
  Abstract  ps  pdf
  

• P. Bürgisser, A. Kurth, A. Wagner
  Incorporating Severity Variations into Credit Risk
  Journal of Risk 3(4): 5-31 (2001)
  Abstract   ps   pdf
  

• P. Bürgisser
  The computational complexity to evaluate representations of general linear groups
  SIAM J. Comp. 30(3):1010-1022 (2000)
  Abstract

• P. Bürgisser
  The computational complexity of immanants
  SIAM J. Comp.30(3):1023-1040 (2000)
  Abstract

• P. Bürgisser
  Cook's versus Valiant's Hypothesis
  Theor. Comp. Sci. 235:71-88 (2000)
  Abstract

• P. Bürgisser
  On the structure of Valiant's complexity classes
  Discr. Math. Theoret. Comp. Sci. 3:73-94 (1999)
  Abstract

• P. Bürgisser
  On the parallel complexity of the polynomial ideal membership problem
  J. Compl. 14:176-189 (1998)
  Abstract   MR 99d:13031

• P. Bürgisser, M. Karpinski, T. Lickteig
  On randomized semialgebraic decision complexity
  J. Compl. 9:231--251 (1993)
  Abstract   MR 94h:68098

• P. Bürgisser, T. Lickteig
  Verification complexity of linear prime ideals
  J. Pure Appl. Alg. 81:247--267 (1992)
  Abstract   MR 94a:68048

• P. Bürgisser, T. Lickteig, M. Shub
  Test complexity of generic polynomials
  J. Compl. 8:203--215 (1992)
  Abstract   MR 93j:68070,

• P. Bürgisser, M. Karpinski, T. Lickteig
  Some computational problems in linear algebra as hard as matrix multiplication
  Comp. Compl. 1:131--155 (1991)
  Abstract   MR 93d:68030

Refereed Contributions in Conference Proceedings

• P. Bürgisser, F. Cucker
  Exotic quantifiers, complexity classes, and complete problems
  Extended abstract in Proc. of ICALP 2007, LNCS 4596, 207-218, 2007.
  ps  pdf
  

• P. Bürgisser, F. Cucker, and P. de Naurois
  The complexity of semilinear problems in succinct representation
  Proceedings of 15th International Symposium on Fundamentals of Computation Theory,
  Lübeck, August 17-20, 2005.
  Lecture Notes in Computer Science 3623, p. 479-490, Springer, 2005.
  Abstract  pdf

• P. Bürgisser, F. Cucker
  Counting Complexity Classes for Numeric Computations
  II: Algebraic and Semialgebraic Sets
  In Proceedings of 36th STOC, pp. 475-485, 2004, Chicago.
  Abstract  ps  pdf
  

• P. Bürgisser, F. Cucker
  Counting Complexity Classes over the Reals I: The Additive Case
  In Proceedings of ISAAC 2003, LNCS 2906, pp. 625-634, Springer, 2003
  Abstract  ps  pdf
  

• P. Bürgisser, M. Lotz
  Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps
  In Proceedings of 43rd FOCS, pp. 658-668, November 16-19, 2002, Vancouver.
  Abstract  ps  pdf

• P. Bürgisser
  Lower Bounds and Real Algebraic Geometry
  In: Algorithmic and Quantitative Real Algebraic Geometry,
  Saugata Basu, Laureano Gonzalez-Vega (eds.),
  DIMACS Series, Volume 60, AMS, pp. 35--54, 2003.
  Abstract  ps  pdf
  Erratum: ps  pdf

• P. Bürgisser
  The Complexity of Factors of Multivariate Polynomials
  Proceedings 42nd FOCS 2001, pp. 378-385, October 14-17, 2001, Las Vegas
  Abstract   ps   pdf
  

• P. Bürgisser, A. Kurth, A. Wagner, M. Wolf
  Credit risk: Integrating correlations
  Risk Magazine 12(7):57-60 (1999)
  Abstract   ps   pdf
  

• P. Bürgisser
  The computational complexity to evaluate representations of general linear groups
  In Proc. 10th International Conference on Formal Power Series and Algebraic Combinatorics,
  Toronto (1998), pp. 115--126.
  Abstract  ps  pdf

• P. Bürgisser
  On the structure of Valiant's complexity classes
  In Proc. 15th Symposium on Theoretical Aspects of Computer Science
  Number 1373 in LNCS, Springer Verlag 1998, pp. 194-204.
  Abstract   ps  pdf  MR 99h:68051

Nonrefereed Contributions

• P. Bürgisser
  On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity (invited paper)
  Proc. 26th Symposium on Mathematical Foundations of Computer Science, Marianske Lazne
  Springer LNCS No. 2136, pp. 3-17, 2001.
  Abstract   ps   pdf

• P. Bürgisser, M. Clausen, M.A. Shokrollahi
  Algebraic Complexity Theory
  In: Handbook of Computer Algebra, pp. 125-128, J. Grabmeier, E. Kaltofen, and V. Weispfenning, eds.
  Springer Verlag, 2003.

• P. Bürgisser, M. Clausen
  Algebraische Komplexitaetstheorie I - Eine Einfuehrung
  Seminaire Lotharingien de Combinatoire, B36a:1--18 (1996)
  MR 68d:68109

• P. Bürgisser
  Algebraische Komplexitaetstheorie II - Schnelle Matrixmultiplikation und Kombinatorik
  Seminaire Lotharingien de Combinatoire, B36b:1--16 (1996)
  MR 68d:68110

Theses

• C. Ikenmeyer
  Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients
  Dissertation, Universität Paderborn (2012)
  pdf

• D. Amelunxen
  Geometric analysis of the condition of the convex feasibility problem
  Dissertation, Universität Paderborn (2011)
  pdf

• C. Ikenmeyer
  On the complexity of computing Kronecker coefficients and deciding positivity of Littlewood-Richardson coefficients
  Diplomarbeit, Universität Paderborn (2008)
  pdf

• P. Bürgisser
  Completeness and Reduction in Algebraic Complexity Theory
  Habilitationsschrift, Universität Zürich (1998)
  Abstract  ps  pdf

• P. Bürgisser
  Degenerationsordnung und Trägerfunktional bilinearer Abbildungen
  Dissertation, Universität Konstanz (1990)
  Konstanzer Schriften in Mathematik und Informatik, Nr. 46
  Abstract  ps  pdf

Unpublished

• P. Bürgisser
  A note on the degeneration order of bilinear maps
  Preprint, University of Zurich (1996)
  Abstract  ps  pdf

• P. Bürgisser
  Decision complexity of generic complete intersections
  Research Report 8578-CS, Institut für Informatik der Universität Bonn (1992)
  Abstract  ps  pdf