Klaus Meer

Adrian Wurm

CoRR, February, 2025

Some Structural Complexity Results for $\exists {\mathbb {R}}$.

[BibT_eX]

[DOI]

Adrian Wurm

Proceedings of the Crossroads of Computability and Logic: Insights, Inspirations, and Innovations, 2025

2024

Software Testing in Computable Analysis.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computation and Natural Computation, 2024

2021

A PCP of Proximity for Real Algebraic Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2021

2019

Interactive proofs and a Shamir-like result for real number computations.

[BibT_eX]

[DOI]

Comput. Complex., 2019

Automata over Infinite Sequences of Reals.

[BibT_eX]

[DOI]

Ameen Naif

Proceedings of the Language and Automata Theory and Applications, 2019

2016

Real Interactive Proofs for VPSPACE.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Periodic Generalized Automata over the Reals.

[BibT_eX]

[DOI]

Ameen Naif

Proceedings of the Language and Automata Theory and Applications, 2016

2015

An Algebraic Proof of the Real Number PCP Theorem.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Some Results on Interactive Proofs for Real Computations.

[BibT_eX]

[DOI]

Proceedings of the Evolving Computability - 11th Conference on Computability in Europe, 2015

2014

Generalized Finite Automata over Real and Complex Numbers.

[BibT_eX]

[DOI]

Ameen Naif

Proceedings of the Theory and Applications of Models of Computation, 2014

Testing Low Degree Trigonometric Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2014

2013

The PCP theorem for NP over the reals.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012

Some Initial Thoughts on Bounded Query Computations over the Reals.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2012

2011

On the expressive power of CNF formulas of bounded tree- and clique-width.

[BibT_eX]

[DOI]

Irénée Briquel

Pascal Koiran

Discret. Appl. Math., 2011

Almost Transparent Short Proofs for NPℝ.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 18th International Symposium, 2011

An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Tree-width in Algebraic Complexity.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2010

2009

On Ladner's Result for a Class of Real Machines with Restricted Use of Constants.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Theory and Computational Practice, 2009

2008

On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width.

[BibT_eX]

[DOI]

Pascal Koiran

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

2007

Simulated Annealing versus Metropolis for a TSP instance.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Some Aspects of a Complexity Theory for Continuous Time Systems.

[BibT_eX]

[DOI]

Marco Gori

Proceedings of the Computation and Logic in the Real World, 2007

2006

Approximation Classes for Real Number Optimization Problems.

[BibT_eX]

[DOI]

Uffe Flarup Hansen

Proceedings of the Unconventional Computation, 5th International Conference, 2006

On the OBDD Size for Graphs of Bounded Tree- and Clique-Width.

[BibT_eX]

[DOI]

Dieter Rautenbach

Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

Uncomputability Below the Real Halting Problem.

[BibT_eX]

[DOI]

Proceedings of the Logical Approaches to Computational Barriers, 2006

Optimization and Approximation Problems Related to Polynomial System Solving.

[BibT_eX]

[DOI]

Proceedings of the Logical Approaches to Computational Barriers, 2006

2005

Computing Minimal Multi-homogeneous Bézout Numbers Is Hard.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

Two Logical Hierarchies of Optimization Problems over the Real Numbers.

[BibT_eX]

[DOI]

Uffe Flarup Hansen

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

An Explicit Solution to Post's Problem over the Reals.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

On Some Relations Between Approximation Problems and PCPs over the Real Numbers.

[BibT_eX]

[DOI]

Proceedings of the New Computational Paradigms, 2005

2004

On a Refined Analysis of Some Problems in Interval Arithmetic Using Real Number Complexity Theory.

[BibT_eX]

[DOI]

Reliab. Comput., 2004

Probabilistically Checkable Proofs Over the Reals.

[BibT_eX]

[DOI]

Proceedings of the 11th Workshop on Logic, Language, Information and Computation, 2004

Computing Multi-Homogeneous Bezout Numbers is Hard

[BibT_eX]

[DOI]

CoRR, 2004

On the Approximation of Interval Functions.

[BibT_eX]

[DOI]

Proceedings of the Applied Parallel Computing, 2004

Transparent Long Proofs: A First PCP Theorem for NPR.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

On the Complexity of Computing Multi-Homogeneous Bézout Numbers.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity for Continuous Problems, 26. September, 2004

04061 Abstracts Collection - Real Computation and Complexity.

[BibT_eX]

[DOI]

Luis Miguel Pardo

Proceedings of the Real Computation and Complexity, 1.-6. February 2004, 2004

04061 Summary - Real Computation and Complexity.

[BibT_eX]

[DOI]

Luis Miguel Pardo

Proceedings of the Real Computation and Complexity, 1.-6. February 2004, 2004

Optimization theory.

[BibT_eX]

Hubertus Th. Jongen

Eberhard Triesch

Kluwer, ISBN: 978-1-4020-8098-2, 2004

2003

On the Complexity of Some Problems in Interval Arithmetic.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2002

A Step towards a Complexity Theory for Analog Systems.

[BibT_eX]

[DOI]

Marco Gori

Math. Log. Q., 2002

Some aspects of studying an optimization or decision problem in different computational models.

[BibT_eX]

[DOI]

Gerhard-Wilhelm Weber

Eur. J. Oper. Res., 2002

On Consistency and Width Notions for Constraint Programs with Algebraic Constraints.

[BibT_eX]

[DOI]

Proceedings of the Functional and Logic Programming, 6th International Symposium, 2002

2000

A Note on Non-complete Problems in NPImage.

[BibT_eX]

[DOI]

Shai Ben-David

Christian Michaux

J. Complex., 2000

On the Complexity of Combinatorial and Metafinite Generating Functions of Graph Properties in the Computational Model of Blum, Shub and Smale.

[BibT_eX]

[DOI]

Johann A. Makowsky

Proceedings of the Computer Science Logic, 2000

1999

On the computational structure of the connected components of a hard problem.

[BibT_eX]

[DOI]

Martín Matamala

Inf. Process. Lett., 1999

Query Languages for Real Number Databases Based on Descriptive Complexity over R.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1999, 1999

1998

On the Structure of NP_C.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

1997

Semi-algebraic Complexity--Additive Complexity of Matrix Computational Tasks.

[BibT_eX]

[DOI]

J. Complex., 1997

Counting Problems over the Reals.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Logics Which Capture Complexity Classes over the Reals.

[BibT_eX]

[DOI]

Felipe Cucker

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

1996

On diagonal sets in uncountable structures.

[BibT_eX]

Proceedings of the Second Workshop on Computability and Complexity in Analysis, 1996

1995

On the Relations Between Discrete and Continuous Complexity Theory.

[BibT_eX]

[DOI]

Math. Log. Q., 1995

A Note on Testing the Resultant.

[BibT_eX]

[DOI]

J. Complex., 1995

Descriptive complexity theory over the real numbers.

[BibT_eX]

[DOI]

Erich Grädel

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

1994

On the Complexity of Quadratic Programming in Real Number Models of Computation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Real Number Computations: On the Use of Information.

[BibT_eX]

[DOI]

J. Symb. Comput., 1994

1993

Komplexitätsbetrachtungen für reelle Maschinenmodelle.

[BibT_eX]

[DOI]

PhD thesis, 1993

Real Number Models under Various Sets of Operations.

[BibT_eX]

[DOI]

J. Complex., 1993

1992

A note on a P NP result for a restricted class of real machines.

[BibT_eX]

[DOI]

J. Complex., 1992

1990

Computations over Z and R: A comparison.

[BibT_eX]

[DOI]