On Mathematics, Complexity and Life

An extended interview with Professor Henryk Woźniakowski, a specialist in computational mathematics, co-author and author of many fundamental information-based complexity (IBC) theorems and researcher in tractability of multivariate problems. Professor Woźniakowski answers the questions concerning mathematics and life with particular emphasis on the period of “Solidarity” and the political changes of the 80s and early 90s of the last century, in which he took an active part. ********* O matematyce, złożoności i życiu. Z Henrykiem Woźniakowskim rozmawiają Bolesław Kacewicz i Leszek Plaskota Wywiad-rzeka z profesorem Henrykiem Woźniakowskim, specjalistą w zakresie matematyki obliczeniowej, współtwórcą i autorem wielu podstawowych twierdzeń teorii analitycznej złożoności obliczeniowej (information-based complexity, IBC) oraz badaczem podatności zadań obliczeniowych zależnych od bardzo wielu zmiennych. Profesor odpowiada na pytania dotyczące jego poglądów na matematykę i życie ze szczególnym uwzględnieniem okresu „Solidarności” i przemian ustrojowych lat 80. i początku lat 90. ubiegłego wieku, w których brał czynny udział.

Professor Henryk Woźniakowski 9 1. The Most Important Thing – Information-Based Complexity 13 2. Childhood and School Years 17 3. Studies at the University of Warsaw 28 4. The Events of March 1968 40 5. First Years of Work 44 6. Numerical Methods in Poland – the Beginnings 49 7. PHD Thesis 58 8. Joseph Traub and Carnegie Mellon 60 9. Health Problems 69 10. Habilitation and Professorship 73 11. Sources and Beginnings of IBC 76 12. IBC in the 1980s 85 13. Discussions with Classical Numerical Analysts 94 14. The Time of the First Solidarity Movement 98 15. The Journal of Complexity 109 16. Monograph: Information-Based Complexity 112 17. Return to Poland 117 18. The Conferences in Dagstuhl 130 19. FoCM and Stephen Smale 138 20. Quantum Computations 147 21. Ian Sloan and his Associates 152 22. Erich Novak and Tractability 158 23. The Honoris Causa Doctorates 167 24. The People of IBC 171 25. The Smolensk Tragedy ´ 178 26. Life Today 185 27. The Future 194 List of Illustrations 204 About the Authors 209