Peter Bürgisser

CoRR, 2024

On the Hardness of PosSLP.

[BibT_eX]

[DOI]

Gorav Jindal

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Real zeros of mixed random fewnomial systems.

[BibT_eX]

[DOI]

Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, 2023

2021

Computing the Homology of Semialgebraic Sets. II: General Formulas.

[BibT_eX]

[DOI]

Josué Tonelli-Cueto

Found. Comput. Math., 2021

Optimization, Complexity and Invariant Theory (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Polynomial Time Algorithms in Invariant Theory for Torus Actions.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

2020

The real tau-conjecture is true on average.

[BibT_eX]

[DOI]

Irénée Briquel

Random Struct. Algorithms, 2020

Computing the Homology of Semialgebraic Sets. I: Lax Formulas.

[BibT_eX]

[DOI]

Josué Tonelli-Cueto

Found. Comput. Math., 2020

Correction To: The Complexity of Factors of Multivariate Polynomials.

[BibT_eX]

[DOI]

Found. Comput. Math., 2020

Rigid continuation paths II. Structured polynomial systems.

[BibT_eX]

[DOI]

Pierre Lairez

CoRR, 2020

Interior-point methods for unconstrained geometric programming and scaling problems.

[BibT_eX]

[DOI]

CoRR, 2020

2019

On the Number of Real Zeros of Random Fewnomials.

[BibT_eX]

[DOI]

Alperen Ali Ergür

Josué Tonelli-Cueto

SIAM J. Appl. Algebra Geom., 2019

Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time.

[BibT_eX]

[DOI]

Pierre Lairez

J. ACM, 2019

Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes.

[BibT_eX]

[DOI]

Cole Franks

CoRR, 2019

Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes.

[BibT_eX]

[DOI]

Cole Franks

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes.

[BibT_eX]

[DOI]

Cole Franks

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Membership in Moment Polytopes is in NP and coNP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Condition of Intersecting a Projective Variety with a Varying Linear Subspace.

[BibT_eX]

[DOI]

SIAM J. Appl. Algebra Geom., 2017

On the condition of the zeros of characteristic polynomials.

[BibT_eX]

[DOI]

Elisa Rocha Cardozo

J. Complex., 2017

2016

Condition Length and Complexity for the Solution of Polynomial Systems.

[BibT_eX]

[DOI]

Found. Comput. Math., 2016

No Occurrence Obstructions in Geometric Complexity Theory.

[BibT_eX]

[DOI]

Greta Panova

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Intrinsic volumes of symmetric cones and applications in convex programming.

[BibT_eX]

[DOI]

Math. Program., 2015

Probabilistic Analysis of the Grassmann Condition Number.

[BibT_eX]

[DOI]

Found. Comput. Math., 2015

Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242).

[BibT_eX]

[DOI]

Marek Karpinski

Nicolai N. Vorobjov Jr.

Dagstuhl Reports, 2015

Permanent versus determinant: not via saturations of monoids of representations.

[BibT_eX]

[DOI]

Jesko Hüttenhain

CoRR, 2015

Fundamental invariants of orbit closures.

[BibT_eX]

[DOI]

CoRR, 2015

Permanent versus determinant, obstructions, and Kronecker coefficients.

[BibT_eX]

[DOI]

CoRR, 2015

Computing the Chow Variety of Quadratic Space Curves.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Aspects of Computer and Information Sciences, 2015

2013

Deciding Positivity of Littlewood-Richardson Coefficients.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Computational Counting (Dagstuhl Seminar 13031).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

Explicit lower bounds via geometric complexity theory.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Condition - The Geometry of Numerical Algorithms.

[BibT_eX]

[DOI]

Grundlehren der mathematischen Wissenschaften 349, Springer, ISBN: 978-3-642-38895-8, 2013

2012

A Coordinate-Free Condition Number for Convex Programming.

[BibT_eX]

[DOI]

SIAM J. Optim., 2012

Robust smoothed analysis of a condition number for linear programming.

[BibT_eX]

[DOI]

Math. Program., 2012

Prospects for Geometric Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to VP≠VNP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Geometric complexity theory and tensor rank.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Probabilistic analysis of condition numbers.

[BibT_eX]

[DOI]

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2011

2010

Smoothed Analysis of Moore-Penrose Inversion.

[BibT_eX]

[DOI]

SIAM J. Matrix Anal. Appl., 2010

Counting Irreducible Components of Complex Algebraic Varieties.

[BibT_eX]

[DOI]

Peter Scheiblechner

Comput. Complex., 2010

Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

10481 Executive Summary - Computational Counting.

[BibT_eX]

[DOI]

Leslie Ann Goldberg

Mark Jerrum

Proceedings of the Computational Counting, 28.11. - 03.12.2010, 2010

10481 Abstracts Collection - Computational Counting.

[BibT_eX]

[DOI]

Leslie Ann Goldberg

Mark Jerrum

Proceedings of the Computational Counting, 28.11. - 03.12.2010, 2010

2009

On the Complexity of Numerical Analysis.

[BibT_eX]

[DOI]

Eric Allender

Johan Kjeldgaard-Pedersen

Peter Bro Miltersen

SIAM J. Comput., 2009

On the complexity of counting components of algebraic varieties.

[BibT_eX]

[DOI]

Peter Scheiblechner

J. Symb. Comput., 2009

Exotic Quantifiers, Complexity Classes, and Complete Problems.

[BibT_eX]

[DOI]

Found. Comput. Math., 2009

An overview of mathematical issues arising in the Geometric complexity theory approach to VP v.s. VNP

[BibT_eX]

[DOI]

CoRR, 2009

On Defining Integers And Proving Arithmetic Circuit Lower Bounds.

[BibT_eX]

[DOI]

Comput. Complex., 2009

2008

The probability that a slightly perturbed numerical analysis problem is difficult.

[BibT_eX]

[DOI]

Math. Comput., 2008

Guest Editor's Preface.

[BibT_eX]

[DOI]

J. Complex., 2008

2007

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties.

[BibT_eX]

[DOI]

Found. Comput. Math., 2007

On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the STACS 2007, 2007

Differential forms in computational algebraic geometry.

[BibT_eX]

[DOI]

Peter Scheiblechner

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2007

2006

Counting complexity classes for numeric computations II: Algebraic and semialgebraic sets.

[BibT_eX]

[DOI]

J. Complex., 2006

On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

The complexity of semilinear problems in succinct representation.

[BibT_eX]

[DOI]

Paulin Jacobé de Naurois

Comput. Complex., 2006

2005

Counting Complexity Classes for Numeric Computations. III: Complex Projective Sets.

[BibT_eX]

[DOI]

Found. Comput. Math., 2005

2004

Lower bounds on the bounded coefficient complexity of bilinear maps.

[BibT_eX]

[DOI]

J. ACM, 2004

The Complexity of Factors of Multivariate Polynomials.

[BibT_eX]

[DOI]

Found. Comput. Math., 2004

2003

Counting Complexity Classes for Numeric Computations I: Semilinear Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Counting Complexity Classes over the Reals I: The Additive Case.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2001

On Implications between P-NP-Hypotheses: Decision versus Computation in Algebraic Complexity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Lower Bounds and Real Algebraic Geometry.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, 2001

2000

Cook's versus Valiant's hypothesis.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

The Computational Complexity of Immanants.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

The Computational Complexity to Evaluate Representations of General Linear Groups.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Completeness and Reduction in Algebraic Complexity Theory.

[BibT_eX]

Algorithms and computation in mathematics 7, Springer, ISBN: 978-3-540-66752-0, 2000

1999

On the Structure of Valiant's Complexity Classes.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 1999

1998

On the Parallel Complexity of the Polynomial Ideal Membership Problem.

[BibT_eX]

[DOI]

J. Complex., 1998

1997

Algebraic complexity theory.

[BibT_eX]

Mohammad Amin Shokrollahi

Michael Clausen

Grundlehren der mathematischen Wissenschaften 315, Springer, ISBN: 3-540-60582-7, 1997

1993

On Randomized Semi-algebraic Test Complexity.

[BibT_eX]

[DOI]

Marek Karpinski

Thomas Lickteig

J. Complex., 1993

1992

Test complexity of generic polynomials.

[BibT_eX]

[DOI]

Thomas Lickteig

Michael Shub

J. Complex., 1992

1991

Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication.

[BibT_eX]

[DOI]