The project comprises of two sub projects:

  • Algorithms and Complexity of Algebraic Problems: This subproject focuses on algebraic problems, more precisely on identity testing problems, arithmetic circuit lower bounds, and isomorphism problems. These are highly relevant problems in current research in theoretical computer science.
    • Investigators on Indian Side: V. Arvind, Meena Mahajan, B. V. Raghavendra Rao, Jayalal Sarma M.N.

    • Investigators on German Side: Markus Blaeser

  • Provably Efficient Preprocessing Algorithms: The focus of this subproject is on parameterized complexity, more speci fically, on kernelization complexity of problems that are fixed parameter tractable. Using tools from parameterized complexity and combinatorics we plan to derive new upper and lower bounds on the kernel sizes for several concrete problems and devise new techniques and tools to obtain upper and lower bounds in general. In particular, we aim to explore deeper connections between extremal graph theory, matroid theory and kernelization for specif c hard problems.
    • Investigators on Indian Side: Venkatesh Raman, Saket Saurabh, John Augustine, Narayanswamy N.S.,

    • Investigators on German Side: Jiong Huo, Martin Doernfelder, Kurt Mehlhorn



No events


  • The deadline for applying for student exchange is March 30, 2015. Students enrolled in a Ph.D. programme at any Indian…
Copyright © 2019 Joomla! demo site. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.