Journal of Complexity, Volume 21

Volume 21, Number 1, February 2005

Foundations of Computational Mathematics Conference 2002

Askold Khovanskii, Pascal Koiran, Teresa Krick, Gregorio Malajovich, Joseph F. Traub:
Guest editors' preface. 4-
Electronic Edition (link) BibTeX
Carlos A. Berenstein, Alekos Vidras, Alain Yger:
Analytic residues along algebraic cycles. 5-42
Electronic Edition (link) BibTeX
Ioannis Z. Emiris, Victor Y. Pan:
Improved algorithms for computing determinants and resultants. 43-71
Electronic Edition (link) BibTeX
Claude-Pierre Jeannerod, Gilles Villard:
Essentially optimal computation of the inverse of generic polynomial matrices. 72-86
Electronic Edition (link) BibTeX
J. Maurice Rojas, Yinyu Ye:
On solving univariate sparse polynomials in logarithmic time. 87-110
Electronic Edition (link) BibTeX
Yosi Yomdin:
Semialgebraic complexity of functions. 111-148
Electronic Edition (link) BibTeX

Volume 21, Number 2, April 2005

Josef Dick, Friedrich Pillichshammer:
Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces. 149-195
Electronic Edition (link) BibTeX
Frances Y. Kuo, Ian H. Sloan:
Quasi-Monte Carlo methods can be efficient for integration over products of spheres. 196-210
Electronic Edition (link) BibTeX
Mark A. Kon, Leszek Plaskota:
Information-based nonlinear approximation: an average case setting. 211-229
Electronic Edition (link) BibTeX
Xiutao Feng, Quanlong Wang, Zongduo Dai:
Multi-sequences with d-perfect property. 230-242
Electronic Edition (link) BibTeX
Gennadi Vainikko, Andi Kivinukk, Jüri Lippus:
Fast solvers of integral equations of the second kind: wavelet methods. 243-273
Electronic Edition (link) BibTeX

Volume 21, Number 3, June 2005

Dany Leviatan, Vladimir N. Temlyakov:
Simultaneous greedy approximation in Banach spaces. 275-293
Electronic Edition (link) BibTeX
Gensun Fang, Fred J. Hickernell, Huan Li:
Approximation on anisotropic Besov classes with mixed norms by standard information. 294-313
Electronic Edition (link) BibTeX
Dennis Cheung, Felipe Cucker:
A note on level-2 condition numbers. 314-319
Electronic Edition (link) BibTeX
Tim Pillards, Ronald Cools:
A note on E. Thiémard's algorithm to compute bounds for the star discrepancy. 320-323
Electronic Edition (link) BibTeX
Wilfried Meidl, Arne Winterhof:
On the joint linear complexity profile of explicit inversive multisequences. 324-336
Electronic Edition (link) BibTeX
Hongwei Sun:
Mercer theorem for RKHS on noncompact sets. 337-349
Electronic Edition (link) BibTeX
Vera Kurková, Marcello Sanguineti:
Learning with generalization capability by kernel methods of bounded complexity. 350-367
Electronic Edition (link) BibTeX

Volume 21, Number 4, August 2005

Festschrift for the 70th Birthday of Arnold Schonhage
Announcements

Stefan Heinrich wins the 2004 Best Paper Award. 369-
Electronic Edition (link) BibTeX
Ian Sloan wins the 2005 Information-Based Complexity Prize. 370-
Electronic Edition (link) BibTeX
2005 Information-Based Complexity Young Researcher Award Committee. 371-
Electronic Edition (link) BibTeX
Thomas Lickteig:
Festschrift in honor of Arnold Scho"nhage. 372-376
Electronic Edition (link) BibTeX

Invited Articles

Bernd Bank, Marc Giusti, Joos Heintz, Luis Miguel Pardo:
Generalized polar varieties: geometry and algorithms. 377-412
Electronic Edition (link) BibTeX
Markus Bläser:
On the number of multiplications needed to invert a monic power series over fields of characteristic two. 413-419
Electronic Edition (link) BibTeX
Alin Bostan, Éric Schost:
Polynomial evaluation and interpolation on special sets of points. 420-446
Electronic Edition (link) BibTeX
Thomas Brihaye, Christian Michaux:
On the expressiveness and decidability of o-minimal hybrid systems. 447-478
Electronic Edition (link) BibTeX
Michel Coste, Tomás Lajous-Loaeza, Henri Lombardi, Marie-Françoise Roy:
Generalized Budan-Fourier theorem and virtual roots. 479-486
Electronic Edition (link) BibTeX
Jean-Pierre Dedieu, Dmitry Nowicki:
Symplectic methods for the approximation of the exponential map and the Newton iteration on Riemannian submanifolds. 487-501
Electronic Edition (link) BibTeX
Mariano De Leo, Ezequiel Dratman, Guillermo Matera:
Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study. 502-531
Electronic Edition (link) BibTeX
Dima Grigoriev:
Weak Bézout inequality for D-modules. 532-542
Electronic Edition (link) BibTeX
Sebastian Heinz:
Complexity of integer quasiconvex polynomial optimization. 543-556
Electronic Edition (link) BibTeX
Armin Hemmerling:
P=NP for some structures over the binary words. 557-578
Electronic Edition (link) BibTeX
Mihai Prunescu:
Two situations with unit-cost: ordered abelian semi-groups and some commutative rings. 579-592
Electronic Edition (link) BibTeX
Andrew J. Sommese, Jan Verschelde, Charles W. Wampler:
An intrinsic homotopy for intersecting algebraic varieties. 593-608
Electronic Edition (link) BibTeX
Arne Storjohann:
The shifted number system for fast linear algebra on integer matrices. 609-650
Electronic Edition (link) BibTeX

Volume 21, Number 5, October 2005

Announcement

2005 Best Paper Award Committee. 651-
Electronic Edition (link) BibTeX

Invited Article

Jean-Claude Yakoubsohn:
Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions. 652-690
Electronic Edition (link) BibTeX
Benjamin Doerr, Michael Gnewuch, Anand Srivastav:
Bounds and constructions for the star-discrepancy via ?-covers. 691-709
Electronic Edition (link) BibTeX

Regular Articles

Shu Tezuka:
On the necessity of low-effective dimension. 710-721
Electronic Edition (link) BibTeX
Fang Gensun, Li Xuehua:
Optimal quadrature problem on Hardy-Sobolev classes. 722-739
Electronic Edition (link) BibTeX
Boleslaw Z. Kacewicz:
Improved bounds on the randomized and quantum complexity of initial-value problems. 740-756
Electronic Edition (link) BibTeX
Kai-Tai Fang, Yu Tang, Jianxing Yin:
Lower bounds for wrap-around L₂-discrepancy and constructions of symmetrical uniform designs. 757-771
Electronic Edition (link) BibTeX

Volume 21, Number 6, December 2005

Mario Wschebor:
On the Kostlan-Shub-Smale model for random polynomial systems. Variance of the number of roots. 773-789
Electronic Edition (link) BibTeX
Kerstin Hesse, Ian H. Sloan:
Optimal lower bounds for cubature error on the sphere S². 790-803
Electronic Edition (link) BibTeX
Fang-Wei Fu, Harald Niederreiter, Ming Su:
The expectation and variance of the joint linear complexity of random periodic multisequences. 804-822
Electronic Edition (link) BibTeX
Claus Scheiderer:
Non-existence of degree bounds for weighted sums of squares representations. 823-844
Electronic Edition (link) BibTeX
Steven B. Damelin, V. Maymeskul:
On point energies, separation radius and mesh norm for s-extremal configurations on compact sets in Rⁿ. 845-863
Electronic Edition (link) BibTeX
Hui Cao:
Discretized Tikhonov-Phillips regularization for a naturally linearized parameter identification problem. 864-877
Electronic Edition (link) BibTeX