Klaus Meer

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

Periodic generalized automata over the reals.

[BibT_eX]

[DOI]

Ameen Naif

Inf. Comput., 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

2017

An algebraic proof of the real number PCP theorem.

[BibT_eX]

[DOI]

J. Complex., 2017

2016

Real Interactive Proofs for VPSPACE.

[BibT_eX]

[DOI]

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

2015

Generalized finite automata over real and complex numbers.

[BibT_eX]

[DOI]

Ameen Naif

Theor. Comput. Sci., 2015

The PCP Theorem for NP Over the Reals.

[BibT_eX]

[DOI]

Found. Comput. Math., 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

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

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Testing Low Degree Trigonometric Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2014

2012

Some Initial Thoughts on Bounded Query Computations over the Reals.

[BibT_eX]

[DOI]

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

On Ladner's result for a class of real machines with restricted use of constants.

[BibT_eX]

[DOI]

Inf. Comput., 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

2010

Tree-width in Algebraic Complexity.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2010

2009

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

[BibT_eX]

[DOI]

Found. Comput. Math., 2009

On the OBDD size for graphs of bounded tree- and clique-width.

[BibT_eX]

[DOI]

Dieter Rautenbach

Discret. Math., 2009

2008

An explicit solution to Post's Problem over the reals.

[BibT_eX]

[DOI]

J. Complex., 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

Some Relations between Approximation Problems and PCPs over the Real Numbers.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Computing Minimal Multi-Homogeneous Bezout Numbers Is Hard.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Simulated Annealing versus Metropolis for a TSP instance.

[BibT_eX]

[DOI]

Inf. Process. Lett., 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

Two logical hierarchies of optimization problems over the real numbers.

[BibT_eX]

[DOI]

Uffe Flarup Hansen

Math. Log. Q., 2006

Approximation Classes for Real Number Optimization Problems.

[BibT_eX]

[DOI]

Uffe Flarup Hansen

Proceedings of the Unconventional Computation, 5th International Conference, 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

Transparent Long Proofs: A First PCP Theorem for NPR.

[BibT_eX]

[DOI]

Found. Comput. Math., 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

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

Counting problems over the reals.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 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

Logics Which Capture Complexity Classes Over The Reals.

[BibT_eX]

[DOI]

Felipe Cucker

J. Symb. Log., 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

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]