max planck institut
informatik

Homepage

Carola Winzen Max-Planck-Institut für Informatik Department 1: Algorithms and Complexity Campus E1 4, Room 329 66123 Saarbrücken Germany Email: winzen "at" mpi-inf.mpg.de Phone: +49 681 9325 1029 Fax: +49 681 9325 1099

---

News

---

• I defended my PhD thesis on December 16, 2011. If you are interested in the thesis or slides, please send me a mail.
• Benjamin and I have some nice topics for Bachelor and Master students. If you are interested, please drop by!

---

Research Interests

---

• Theory of randomized search heuristics
• (Randomized) Query complexity
• Geometric discrepancies
• Randomized and quasi-randomized algorithms

---

Publications

---

Journal Articles:

• [SIAM JoNA 2012+] M. Gnewuch, Magnus Wahlström, and C. Winzen.
  A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting.
  SIAM Journal on Numerical Analysis, to appear.
  Extended authors generated version.
  
  
• [Algorithmica 2012+] B. Doerr, D. Johannsen, and C. Winzen.
  Multiplicative Drift Analysis.
  Algorithmica, to appear.
  arXiv version.
  
  
• [TCS 2012+] B. Doerr, D. Johannsen, and C. Winzen.
  Non-Existence of Universal Drift Functions.
  Theoretical Computer Science, to appear.
  arXiv version.
  
  
• [IPL 2012] B. Doerr and C. Winzen.
  Memory-Restricted Black-Box Complexity of OneMax.
  Information Processing Letters, Volume 112, pages 32-34, Elsevier, 2012.
  Official link. ECCC version.
  
  
• [ECJ 2012] B. Doerr, T. Jansen, D. Sudholt, C. Winzen, and C. Zarges.
  Mutation Rate Matters Even When Optimizing Monotone Functions.
  Evolutionary Computation, to appear.
  arXiv version.
  
  
• [J. Complexity 2009] M. Gnewuch, A. Srivastav, and C. Winzen.
  Finding optimal volume subintervals with k points and calculating the star discrepancy are NP-hard problems.
  Journal of Complexity, Volume 25, pages 115-127, Elsevier, 2009.
  authors generated version. official link.
  
  

Articles in Proceedings of Refereed Conferences:

• [STACS 2012] B. Doerr and C. Winzen.
  Playing Mastermind With Constant-Size Memory.
  arXiv version. To appear.
  
  
• [GECCO 2011] B. Doerr, T. Kötzing, and C. Winzen.
  Too Fast Unbiased Black-Box Algorithms.
  In: Proc. of Genetic and Evolutionary Computation Conference (GECCO 2011), pages 2043-2050, ACM, 2011.
  official link.
  
  
• [GECCO 2011] B. Doerr, T. Kötzing, J. Lengler, and C. Winzen.
  Black-Box Complexities of Combinatorial Problems.
  In: Proc. of Genetic and Evolutionary Computation Conference (GECCO 2011), pages 981-988, ACM, 2011.
  arXiv version. official link.
  
  
• [CSR 2011] B. Doerr and C. Winzen.
  Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity.
  In: Proc. of 6th International Computer Science Symposium in Russia (CSR 2011), pages 15-28, Springer, 2011.
  arXiv version. official link.
  
  
• [EA 2011] B. Doerr and C. Winzen.
  Black-Box Complexity: Breaking the O(n log n) Barrier of LeadingOnes.
  Proceedings of Artificial Evolution (EA 2011).
  
  
• [FOGA 2011] B. Doerr, D. Johannsen, T. Kötzing, P. K. Lehre, M. Wagner, and C. Winzen.
  Faster Black-Box Algorithms Through Higher Arity Operators.
  In: Proc. of Foundations of Genetic Algorithms XI (FOGA 2011), pages 163-172, ACM, 2011.
  arXiv version. official link.
  
  
• [PPSN 2010] B. Doerr, T. Jansen, D. Sudholt, C. Winzen, and C. Zarges.
  Optimizing Monotone Functions Can Be Difficult.
  In: Proc. of Parallel Problem Solving from Nature (PPSN 2010). LNCS 6238, pages 42-51, Springer, 2010.
  official link.
  
  
• [GECCO 2010] B. Doerr, D. Johannsen, and C. Winzen.
  Multiplicative Drift Analysis.
  In: Proc. of Genetic and Evolutionary Computation Conference (GECCO 2010), pages 1449-1456, ACM, 2010. Best Paper Award in the 'Theory' track.
  official link.
  
  
• [CEC 2010] B. Doerr, D. Johannsen, and C. Winzen.
  Drift Analysis and Linear Functions Revisited.
  In: Proc. of the IEEE Congress on Evolutionary Computation (CEC 2010), pages 1967-1974, IEEE, 2010.
  official link.
  
  

Preprints:

• [Preprint 2012] B. Doerr, T. Kötzing, J. Lengler, and C. Winzen.
  Black-Box Complexities of Combinatorial Problems.
  arXiv version. Submitted (journal).
  
  
• [Preprint 2011] B. Doerr and C. Winzen.
  Ranking-Based Black-Box Complexity.
  arXiv version. Submitted (journal).
  
  
• [Preprint 2011] C. Winzen.
  Direction-Reversing Quasi-Random Rumor Spreading with Restarts.
  arXiv version. Submitted (journal).
  
  

Theses:

• [Thesis 2011] C. Winzen.
  Toward a Complexity Theory for Randomized Search Heuristics: Black-Box Models.
  Dissertation. Universität des Saarlandes, Saarbrücken, Germany, 2011.
  If you are interested in the thesis or the slides, please send me a mail. I will be happy to share it.
  
  
• [Thesis 2007] C. Winzen.
  Approximative Berechnung der Sterndiskrepanz.
  Diplomarbeit. Christian-Albrechts-Universität zu Kiel, 2007.
  Published version: Approximative Berechnung der Sterndiskrepanz: Theorie und Heuristik. VDM Verlag Dr. Müller, 2010.
  
  

Other Conference and Workshop Presentations (Selection):

• [MCQMC 2012] M. Gnewuch, Magnus Wahlström, and C. Winzen.
  Computing Star Discrepancies via a Refined Threshold Accepting Heuristic.
  To be presented at the 10th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC 2012).
  
  
• [ThRaSH 2011] B. Doerr and C. Winzen.
  Black-Box Models with Restricted Memory.
  Presented at 5th Workshop on Theory of Randomized Search Heuristics (ThRaSH 2011). Slides
  
  
• [Dagstuhl Seminar 10361, 2010] C. Winzen.
  Monotone Black-Box and Higher arity Black-Box Complexities.
  Presented at Dagstuhl Seminar 10361 on Theory of Evolutionary Algorithms (Dagstuhl 2010).
  
  
• [KolKom 2010] C. Winzen.
  Black-Box Complexities for Randomized Search Heuristics.
  Presented at Colloquium on Combinatorics (KolKom 2010). Booklet with Abstracts.
  
  
• [ThRaSH 2010] B. Doerr, D. Johannsen, and C. Winzen.
  Linear Functions Revisited.
  Presented at 4th Workshop on Theory of Randomized Search Heuristics (ThRaSH 2010). Slides
  
  

---

Teaching

---

Courses:

• Summer Semester 2012: Co-organizer of the lecture Basic Mathematical Techniques for Computer Scientists, together with Timo Kötzing, Xavier Pèrez-Gimènez, Chandan Saha, Thomas Sauerwald, Reto Spöhel, and Jens Schmidt
• Summer Semester 2012: Co-organizer of the seminar Reading Group in Algorithms, together with Kurt Mehlhorn.
• Winter Semester 2011/12: Co-organizer of the seminar Reading Group in Algorithms, together with Kurt Mehlhorn.
• Summer Semester 2011: Co-organizer of the seminar Reading Group in Algorithms, together with Kurt Mehlhorn.
• Summer Semester 2010: Teaching assistant for Algorithms and Randomization held by Chinmoy Dutta, Nikolaos Fountoulakis, and Anna Huber.
• Winter Semester 2004 - Winter Semester 2006: Teaching assistant for various courses held by the department for mathematics at Kiel University

Students:

• Co-Advisor of the master student Vijay Ingalalli.
  Title of the thesis: Evolutionary Algorithms to Compute Lower Bounds for the Star Discrepancy
• Co-Advisor of the intern Jong-Hyun Lee.
  

---

Academic Activities

---

• Program Committees: GECCO 2012, PPSN 2012, GECCO 2011.
• Organinzing Committees: Colloquium on Combinatorics KolKom 2012, Colloquium on Combinatorics KolKom 2010.
• Journal Reviews: Theory of Computing Systems, Information Processing Letters.
• Conference Reviews: STACS 2012, RANDOM 2011, STACS 2011, FOGA 2011, CEC 2011, PPSN 2010.
• Reviews of book chapters: Runtime Analysis of Evolutionary Algorithms for Discrete Optimization, written by Pietro S. Oliveto and Xin Yao, published in Theory of Randomized Search Heuristics, Foundations and Recent Developments by Anne Auger and Benjamin Doerr (editors).

---

Short CV

---

• Since January 2012:
  Postdoctoral researcher at the Max-Planck-Institut für Informatik
  
• January 2010 - December 2011:
  Ph. D. student in Computer Science at the Universität des Saarlandes, Saarbrücken, Germany and the Max-Planck-Institut für Informatik
  My work is supported by the Google Europe Fellowship in Randomized Algorithms (click here for program details)
• December 2007 - January 2012:
  Management consultant with McKinsey&Company, Inc.. Main focus: network optimization and scheduling for clients in the transportation and logistics industry.
• August 2007:
  Diploma in Mathematics at the Christian-Albrechts-Universität (CAU) Kiel
  Title of my diploma thesis: Approximative Berechnung der Sterndiskrepanz (advisor: Dr. Michael Gnewuch, supervisor: Prof. Dr. Anand Srivastav)
• July 2006 - October 2006:
  Internship with Deutsche Lufthansa AG
• October 2003 - August 2007:
  Studies of Mathematics (major subject), Business Administration (minor subject, Studienkolleg), Economics (Vordiplom, for fun), and Computer Science (for fun) at the CAU Kiel
  My studies were supported by a stipend of the Klaus Murmann Fellowship Programme of the Foundation of German Business/ Studienförderwerk Klaus Murmann der Stiftung der Deutschen Wirtschaft (SDW)
• July 2003:
  Abitur at the Heinrich-Suso-Gymnasium, Konstanz
• August 2000 - July 2001:
  AFS high school exchange student in Tobati, Paraguay.

• Carola Winzen:
• Research Interests
• Publications
• Teaching
• Academic Activities
• Short CV