Information-Based Complexity

Awards and Prizes

There are three prizes that are especially pertinent to researchers in IBC.

Prize for Achievement in Information-Based Complexity

This annual prize is for outstanding achievement in information-based complexity. This award consists of $3,000 and a plaque.

The awardees have been:

• 2008: Anargyros Papageorgiou (Columbia University)
• 2007: Klaus Ritter (TU Darmstadt)
• 2006: Leszek Plaskota (University of Warsaw)
• 2005: Ian H. Sloan (University of New South Wales).
• 2004: Peter Mathé (Weierstrass Institute for Applied Analysis and Stochastics)
• 2003: Arthur G. Werschulz (Fordham University)
• 2002: Stephan Heinrich (University of Kaiserslautern)
• 2001: Greg Wasilkowski (University of Kentucky)
• 2000: Sergei Pereverzev (Ukrainian Academy of Science)
• 1999: Erich Novak (University of Jena)

Information-Based Complexity Young Researcher Award

This annual prize is for significant contributions to information-based complexity by a young researcher who has not reached his or her 35th birthday by September 30th of the year of the award. This award consists of $1,000 and a plaque.

The awardees have been:

• 2007: Andreas Neuenkirch (University of Frankfurt)
• 2006: Jakob Creutzig (TU Darmstad) and Dirk Nuyens (Katholieke Universiteit, Leuven)
• 2005: Friedrich Pillichshammer (University of Linz)
• 2004: Christine Lemieux (University of Calgary) and Josef Dick (University of New South Wales)
• 2003: Frances Kuo (University of New South Wales)

Best Paper Award, Journal of Complexity

This annual prize is for the best paper published by the Journal of Complexity during any particular year. It consists of $3,000 and a plaque.

The awardees have been:

• 2007: Two papers were chosen as co-winners:
  • Martin Avendano and Teresa Krick (Universidad de Buenos AIres) and Martin Sombra, Factoring bivariate sparse (lacunary) polynomials
  • Istvan Berkes and Robert F. Tichy (Techincal University Graz) and the late Walter Philipp (University of Illinois), Psuedorandom nunmbers and entropy conditions
• 2006: Knut Petras and Klaus Ritter, On the complexity of parabolic initial-value problems with variable drift
• 2005: Two papers were chosen as co-winners:
  • Y.Yomdin, Semialgebraic complexity of functions
  • J.Dick and F.Pillichshammer, Multivariate integration in weighted Hilbert spaces based on Walsh functions
• 2004:Stefan Heinrich, Quantum Approximation I. Embeddings of Finite-Dimensional $L_p$ Spaces and Quantum Approximation II. Sobolev Embeddings
• 2003: Two papers were chosen as co-winners:
  • Markus Blaeser, On the complexity of the multiplication of matrices of small formats
  • Boleslaw Kacewicz, How to minimize the cost of iterative methods in the presence of pertubations
• 2002: P. Hertling, Topological Complexity of Zero Finding with Algebraic Operations
• 2001: E. Novak, Quantum Complexity of Integration
• 2000: Two papers were chosen as co-winners:
  • B. Mourrain and V. Y. Pan, Multivariate Polynomials, Duality and Structured Matrices
  • J. M. Rojas, Some Speed-Ups and Speed Limits for Real Algebraic Geometry
• 1999: A. G. Werschulz, Where Does Smoothness Count the Most for Two-Point Boundary Value Problems?
• 1998: Two papers were chosen as co-winners.
  • S. Heinrich, Monte Carlo Complexiy of Global Solution of Integral Equations
  • P. Kirrinis, Partial Fraction Decomposition in C(z) and Simultaneous Newton Iteration for Factorization in C(z)
• 1997: Two papers were chosen as co-winners:
  • B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop, Polar Varieties, Real Equation Solving, and Data Structures: The Hypersurface Case
  • R. DeVore and V. Temlyakov, Nonlinear Approximation in Finite Dimensional Spaces
• 1996: P. Koiran, Hilbert´s Nullstellensatz is in the Polynomial Hierarchy