Journal of  Complexity  Award

Best Paper Award, Journal of Complexity

In 1996 the Journal of Complexity instituted an annual Best Paper Award consisting of a prize of three thousand dollars ($3,000) and a plaque.

1996 Award

Winner:

Pascal Koiran

Title:

Hilbert´s Nullstellensatz is in the Polynomial Hierarchy

Publication:

December, 1996

Committee:

Stefan Heinrich and Steven Smale

1997 Award

Two papers were chosen as co-winners

Co-Winner:

B. Bank, M. Giusti, J. Heintz, and G. M. Mbakop

Title:

Polar Varieties, Real Equation Solving, and Data Structures: The Hypersurface Case

Publication:

March, 1997

Co-Winner:

R. DeVore and V. Temlyakov

Title:

Nonlinear Approximation in Finite Dimensional Spaces

Publication:

December, 1997

Committee:

Wolfgang Dahmen and Jean-Pierre Dedieu

1998 Award

Two papers were chosen as co-winners

Co-Winner:

S. Heinrich

Title:

Monte Carlo Complexity of Global Solution of Integral Equations

Publication:

June, 1998

Co-Winner:

P. Kirrinis

Title:

Partial Fraction Decomposition in C(z) and Simultaneous Newton Iteration for Factorization in C(z)

Publication:

September, 1998

Committee:

Felipe Cucker and Greg Wasilkowski

Both authors receive a certificate and their share of the $3000 prize, presented at the Foundations of Computational Mathematics Conference in Oxford, England, in July, 1999.

1999 Award

Winner:

Arthur G. Werschulz

Title:

Where Does Smoothness Count the Most for Two-Point Boundary-Value Problems?

Publication:

September 1999

Committee:

Leszek Plaskota and Klaus Ritter

2000 Award

Two papers were chosen as co-winners

Co-Winner:

Bernard Mourrain and Victor Y. Pan

Title:

Multivariate Polynomials, Duality, and Structured Matrices

Publication:

March 2000

Co-Winner:

J. Maurice Rojas

Title:

Some Speed-Ups and Speed Limits for Real Algebraic Geometry

Publication:

September 2000

Committee:

Erich Novak and Vladimir Temlyakov

Each author will receive a plaque and a third of the $3000 prize. The award was presented at the Foundations of Computational Mathematics Conference in Minneapolis, in August, 2002.

2001 Award

Winner:

Erich Novak

Title:

Quantum Complexity of Integration

Publication:

March 2001

Committee:

Ian Sloan and Arthur G. Werschulz

The award was presented at the Foundations of Computational Mathematics Conference in Minneapolis, in August, 2002.

2002 Award

Winner:

Peter Hertling

Title:

Topological Complexity of Zero Finding with Algebraic Operations

Publication:

December 2002

Committee:

Fred J. Hickernell and Peter Mathe

The award was presented at the Conference on Modern Computational Methods in Applied Mathematics, Stefan Banach International Mathematical Center, Bedlweo, Poland, June 2004.

2003 Award

Two papers were chosen as co-winners

Co-Winner:

Markus Blaeser

Title:

On the complexity of the multiplication of matrices of small formats

Publication:

February 2003

Co-Winner:

Boleslaw Kacewicz

Title:

How to minimize the cost of iterative methods in the presence of pertubations

Publication:

February 2003

Committee:

Thomas Mueller-Gronbach and Sergei Pereverzev

Each author received a check for $1500 and a plaque.

2004 Award

Winner:

Stefan Heinrich

Title:

Quantum Approximation I. Embeddings of Finit-Dimensional Lp Spaces
Quantum Approximation II. Sobolev Embeddings

Publication:

February 2004

Committee:

Boleslaw Kacewicz and Peter Hertling

The award was presented at the Foundations of Computational Mathematics Conference in Santander, Spain, in June, 2005.

2005 Award

Two papers were chosen as co-winners

Co-Winner:

Yosef Yomdin

Title:

Semialgebraic complexity of functions

Publication:

February 2005

Co-Winners:

 Josef Dick and Friedrich Pillichshammer

Title:

Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces

Publication:

April 2005

Committee:

Luis M. Pardo and Kris Sikorski

The authors will split the $3000 and each will receive a plaque.

2006 Award

Winner:

Knut Petras and Klaus Ritter

Title:

On the complexity of parabolic initial value problems with variable drift

Publication:

February 2006

Committee:

Klaus Meer and Shu Tezuka

The authors will split the $3000 and each will receive a plaque.

2007 Award

Two papers were chosen as co-winners

Co-Winner:

Martin Avendano, Teresa Krick and Martin Sombra

Title:

Factoring bivariate sparse (lacunary) polynomials

Publication:

April 2007

Co-Winners:

Istvan Berkes, Robert F. Tichy and the late Walter Philipp

Title:

Pseudorandom numbers and entropy conditions

Publication:

August - December, 2007

Committee:

Thomas Lickteig and Anargyros Papageorgiou

The authors will split the $3000 and each will receive a plaque.

2008 Award

Winner:

Stefan Heinrich and Bernhard Milla

Title:

The randomized complexity of initial value problems

Publication:

April 2008

Committee:

Ronald Cools and Mario Milanese

The authors will split the $3000 and each will receive a plaque.

2009 Award

Winner:

Frank Aurzada, Steffen Dereich, Michael Scheutzow and Christian Vormoor

Title:

High resolution quantization and entropy coding of jump processes

Publication:

April 2009

Committee:

Stephan Dahlke and Josef Dick

The authors will split the $3000 and each will receive a plaque.

2010 Award

Two papers were chosen as co-winners

Co-Winner:

Aicke Hinrichs

Title:

Optimal importance sampling for the approximation of integrals

Publication:

April 2010

Co-Winners:

Simon Foucart, Alain Pajor, Holger Rauhut, Tino Ullrich

Title:

The Gelfand widths of lp-balls for 0 < p = 1

Publication:

December 2010

Committee:

Steffen Dereich and Frances Kuo

The authors will split the $3000 and each will receive a plaque.

2011 Award

Two papers were chosen as co-winners

Co-Winner:

Thomas Daun

Title:

On the randomized solution of initial value problems

Publication:

August 2011

Co-Winners:

Leszek Plaskota, Greg W. Wasilkowski

Title:

Tractability of infinite-dimensional integration in the worst case and randomized settings

Publication:

December 2011

Committee:

Aicke Hinrichs and Stephen Joe

The authors will split the $3000 and each will receive a plaque.

2012 Award

Two papers were chosen as co-winners

Co-Winner:

Dmitriy Bilyk, V.N. Temlyakov, Rui Yu

Title:

Fibonacci sets and symmetrization in discrepancy theory

Publication:

February 2012

Co-Winners:

Lutz Kämmerer, Stefan Kunis, Daniel Potts

Title:

Interpolation lattices for hyperbolic cross trigonometric polynomials

Publication:

February 2012

Committee:

Mikhail Lifshits and Art Owen

The authors will split the $3000 and each will receive a plaque.

2013 Award

Committee:

TBA