max planck institut
informatik

Homepage

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

---

News

---

• I recently moved to office 313 (Kosta's old office).
• Benjamin and I have some nice topics for Bachelor and Master students. If you are interested, please drop by!

---

Research Interests

---

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

---

Publications

---

Journal Articles:

• [SIAM JoNA 2012] M. Gnewuch, M. Wahlström, and C. Winzen.
  A New Randomized Algorithm to Approximate the Star Discrepancy Based on Threshold Accepting.
  SIAM Journal on Numerical Analysis, Volume 50, pages 781-807, SIAM Society for Industrial and Applied Mathematics, 2012.
  official link. Extended authors generated version.
  
  
• [Algorithmica 2012+] B. Doerr, D. Johannsen, and C. Winzen.
  Multiplicative Drift Analysis.
  Algorithmica (special issue on evolutionary computation), to appear.
  arXiv version.
  
  
• [TCS 2012] B. Doerr, D. Johannsen, and C. Winzen.
  Non-Existence of Universal Drift Functions.
  Theoretical Computer Science, Volume 436, pages 71-86, Elsevier, 2012.
  Official link. 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:

• [CTW 2012] B. Doerr, R. Spöhel, H. Thomas and C. Winzen.
  Playing Mastermind with Many Colors.
  Short abstract in Proc. of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012), to appear.
  
  
• [GECCO 2012] B. Doerr and C. Winzen.
  Reducing the Arity in Unbiased Black-Box Complexity.
  In: Proc. of Genetic and Evolutionary Computation Conference (GECCO 2012), to appear.
  arXiv version.
  
  
• [STACS 2012] B. Doerr and C. Winzen.
  Playing Mastermind With Constant-Size Memory.
  In: Proc. of Symposium on Theoretical Aspects of Computer Science (STACS 2012), pages 441-452, LIPIcs, 2012.
  arXiv version. The paper has been invited to the ToCS special issue.
  
  
• [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). Springer, to appear.
  
  
• [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.
  arXiv version. 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.
  arXiv version. 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 and C. Winzen.
  Playing Mastermind with Constant-Size Memory.
  arXiv version. Invited submission to the ToCS special issue of STACS 2012.
  
  
• [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:

• [PhD 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.
  Here is a short (non-scientific) article about my thesis (in German). This one here (also in German) is a bit more detailed.
  
  
• [Diplom 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.
  If you are interested in the thesis, please send me a mail. I will be happy to share it. Please note that the thesis is in German.
  
  

Other Conference and Workshop Presentations (Selection):

• [MCQMC 2012] M. Gnewuch, M. Wahlström, and C. Winzen.
  Computing Star Discrepancies via a Refined Threshold Accepting Heuristic.
  Presented at the 10th International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC 2012). Slides.
  
  
• [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.
  Title of the project: Playing Mastermind with Constant Size Memory

---

Academic Activities

---

• Program Committees: GECCO 2012, PPSN 2012, GECCO 2011.
• Organinzing Committees: Colloquium on Combinatorics KolKom 2010.
• Journal Reviews: Theory of Computing Systems, Information Processing Letters.
• Conference Reviews: RANDOM 2012, ICALP 2012, 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 Ph. D. studies were supported by the Google Europe Fellowship in Randomized Algorithms (click here for program details)
• December 2007 - January 2012:
  Consultant with McKinsey&Company, Inc., Munich. From December 2009 until January 2012, I was on educational leave.
• 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