Fine-grained complexity of algorithm and data structures is a new area with flourishing activity. Analogous to NP-completeness, fine-grained complexity relies on a few carefully chosen conjectures to prove conditional lower bounds for fundamental algorithmic and data structural problems. Some of the most important results in the area include quadratic lower bounds for classic problems such as edit distance, longest common subsequence and various polynomial lower bounds for dynamic data structures and the like. Of course, the long term goal is to replace these conditional lower bounds with unconditional ones, but this is far out of reach with current techniques.
Starting August 1, 2016 or later, a Ph.D. student and a Post Doc position is available under the supervision of Assistant Professor Kasper Green Larsen (www.cs.au.dk/~larsen).
The positions are within (but not limited to) the area of computational complexity of algorithms and data structures. The selected candidates will work mainly on fine-grained complexity in the form of proving conditional lower bounds and understanding the connections between different hardness conjectures. Secondly, the chosen candidates will also work on improving the current techniques for proving unconditional lower bounds - in particular for data structures, which is an area where we can in fact prove interesting and non-trivial unconditional lower bounds. The candidates are also free to pursue other interesting research questions in related areas.
The research will be carried out at the Department of Computer Science at Aarhus University, Denmark under the supervision of Assistant Professor Kasper Green Larsen. The positions will also be associated with the
Center for Massive Data Algorithmics (MADALGO). MADALGO is a basic research
center funded by the Danish National Research Foundation. The center is
located in the Department of Computer Science, Aarhus University,
Denmark, but also includes researchers at CSAIL, Massachusetts Institute
of Technology, at the Max Planck Institute for Informatics and at
Frankfurt University. The center covers all areas of the design,
analysis and implementation of algorithms and data structures for
processing massive data (interpreted broadly to cover computations where
data is large compared to the computational resources), with focus on
I/O-efficient, cache-oblivious and streaming algorithms.
See www.madalgo.au.dk for more information.
The Ph.D. positions are
administered through Graduate School of Science and Technology at Aarhus
University (talent.au.dk/phd/scienceandtechnology) and include full
tuition waiver and a very competitive scholarship. Applications are
welcomed from students with at least three years of full-time study by
August 2016. Students with a strong background in complexity theory and/or algorithms will be preferred.
One Post Doc position at the level of Research Assistant
Professor of Computer Science is also available. Postdoc positions are
initially for one year, but can be extended with an additional year by
mutual consent. We welcome postdoctoral researchers with clearly
demonstrated experience and skills in the areas of computational complexity, algorithms and/or data structures. The responsibilities of Post Docs may include modest teaching responsibilities.
The application deadline for both Ph.D. student and Post Doc positions is May
1, 2016. Applicants for Ph.D. student positions should apply using the
Aarhus Graduate School of Science and Technology application system also
accessible from www.madalgo.au.dk. Applicants for Post Doc positions
should apply by uploading a letter of interest and a CV, as well as
indicate at least two names of references for recommendations, using the
application form available at www.madalgo.au.dk.
For further information, contact Assistant Professor Kasper Green Larsen
at larsen@cs.au.dk.
Best regards/Mvh
Kasper Green Larsen
Assistant Professor, Ph.D.
Department of Computer Science
Aarhus University
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
