BrainMap

Gabriel Istrate

- INSTITUTUL E - AUSTRIA TIMISOARA

Expertise & keywords

Structure and intractability in combinatorial optimization: an interdisciplinary approach Call name: Exploratory Research Projects - PCE-2011 call
PN-II-ID-PCE-2011-3-0981 2012 - 2016

Role in this project:

Coordinating institution: Institutul e-Austria Timisoara

Project partners: Institutul e-Austria Timisoara (RO)

Affiliation: Institutul e-Austria Timisoara (RO)

Project website: http://tcs.ieat.ro/grants/idei-2012/

Abstract:

Combinatorial Optimization and Computational Complexity have greatly benefitted from considering combinatorial problems from a probabilistic rather than worst-case perspective. A theory of Phase Transitions in Combinatorial Problems has emerged as an interdisciplinary field combining ideas from physics, Theoretical Computer Science and A.I. and mathematics.

Inspired by this theory we aim to develop a better understanding of the impact that

- the structure of the solution space (for satisfiable instances)

- and of “obstructions” to satisfiability (for unsatisfiable ones)

have on algorithmic performance in combinatorial optimization.
While inspired by the theory of phase transitions, we aim substantially extend it and make it more systematic.

From a technical standpoint the approach we propose involves two significant ingredients:

1. the use of logic-based methods for classification. Logic plays a dual role: to specify classes of problems (via finite model theory); and to specify classes of algorithms (via proof complexity).

2. second, we will employ results/methods from combinatorial algebraic topology in the study of (topological) obstructions to satisfiability.

The motivating observation is that topological objects appearing in the study of obstructions live in a space of "generalized solutions" similar to the "solution covers" from so-called clustering phase transitions. Also, both are concerned with structural properties such as connectivity.

Call name: Premierea obtinerii atestatului de abilitare - Competitia 2015
PN-II-RU-ABIL-2015-2-0272 2015 -

Role in this project:

Coordinating institution: UNIVERSITATEA DE VEST TIMISOARA

Project partners: UNIVERSITATEA DE VEST TIMISOARA (RO)

Affiliation: UNIVERSITATEA DE VEST TIMISOARA (RO)

Project website:

Abstract:

FILE DESCRIPTION	DOCUMENT
List of research grants as project coordinator
List of research grants as partner team leader
List of research grants as project coordinator or partner team leader
Significant R&D projects for enterprises, as project manager
R&D activities in enterprises
Peer-review activity for international programs/projects