Log In
Sign Up
Romania
Citizenship:
Ph.D. degree award:
Gabriel
Istrate
-
INSTITUTUL E - AUSTRIA TIMISOARA
Personal public profile link.
Expertise & keywords
Projects
Publications & Patents
Entrepreneurship
Reviewer section
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.
Read more
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:
Read more
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
[T: 0.2871, O: 247]