1. Classes of combinatorial objects: from structure to algorithms (CCOSA); ERC-2010-StG_20091028; 60 months; 01/12/2010 - 30/11/2015; Doc. Daniel Král, PhD.; MFF
Od 1.9. 2012 odchází doc. Král s ERC grantem na University of Warwick (UK)
2. Ion Spectroscopy of Reaction Intermediates(ISORI); ERC-2010-StG_20091028; 60 months; 01/01/2011 - 31/12/2016; Doc. Jana Roithová, Ph.D.; PřF
Modern chemistry experiences a fast development of new reactions with dominance in organometallics and recently also organocatalysis. The massive synthetic progress however greatly foreruns mechanistic studies and the deeper insight is often rather limited. This large unexplored area accordingly challenges pioneering research and formulation of new concepts in chemistry. The present research project uses the most powerful tools of several research disciplines and aims towards the investigation of the elementary steps in organic reactions by means of mass spectrometry (MS) in combination with electrospray ionization (ESI) and quantum chemistry with a particular focus on ion spectroscopy. The research will concentrate on elementary reactions in catalysis, e.g. the interaction of catalysts with substrates or bimolecular reactions of reactant/catalyst complexes. A major innovative contribution consists in applying ion spectroscopy for the structural characterization of reaction intermediates using a newly proposed tandem mass spectrometer with a cooled linear ion trap, which will allow two-photon experiments with IR and UV tunable lasers. The experiments will provide specific information about various intermediates and will help to disentangle even complicated mixtures or isomeric ions. In addition, an innovative experiment is designed, in which bimolecular reactivity of isobaric ions will be studied individually. Kinetics of selected reactions in solution will also be followed by ESI/MS. The combined efforts of these different approaches will provide a comprehensive understanding of the reaction mechanisms and will lead to the formulation of new general concepts in organic and organometallic reactivity.
3. Lower bounds for combinatorial algorithms and dynamic problems (LBCAD); ERC-2013-CoG; 01/02/2014 - 31/01/2019; doc. Mgr. Michal Koucký, Ph.D.; MFF
This project aims to establish the time complexity of algorithms for two classes of problems. The first class consists of problems related to Boolean matrix multiplication and matrix multiplication over various semirings. This class contains problems such as computing transitive closure of a graph and determining the minimum distance between all-pairs of nodes in a graph. Known combinatorial algorithms for these problems run in slightly sub-cubic time. By combinatorial algorithms we mean algorithms that do not rely on the fast matrix multiplication over rings. Our goal is to show that the known combinatorial algorithms for these problems are essentially optimal. This requires designing a model of combinatorial algorithms and proving almost cubic lower bounds in it. The other class of problems that we will focus on contains dynamic data structure problems such as dynamic graph reachability and related problems. Known algorithms for these problems exhibit trade-off between the query time and the update time, where at least one of them is always polynomial. Our goal is to show that indeed any algorithm for these problems must have update time or query time at least polynomial. The two classes of problems are closely associated with so called 3SUM problem which serves as a benchmark for uncomputability in sub-quadratic time. Our goal is to deepen and extend the known connections between 3SUM, the other two classes and problems like formula satisfiability (SAT).