BrainMap

Gabriel Istrate

- INSTITUTUL E - AUSTRIA TIMISOARA

Expertise & keywords

Advanced techniques in optimization and computational complexity Call name: P 4 - Proiecte de Cercetare Exploratorie
PN-III-P4-ID-PCE-2016-0842 2017 - 2019

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://gabrielistrate.wordpress.com/idei-2016/

Abstract:

The goal of the project is to contribute to the development and application of timely, sophisticated techniques for improving the analysis of problems in Combinatorial Optimization and Computational Complexity. Building on recent progress by the PI and members of the team, we aim to

- provide a better understanding of the proof complexity of combinatorial principles and of noneffective propositional proof methods.

- devise methods for investigating the complexity of smoothed and continuously perturbed combinatorial problems, including versions of satisfiability.

- contribute to the theory of submodular optimization by studying extensions of the notion (and their algorithmic implications), as well as structural parameters (e.g. VC dimension) that may lead to different algorithms than the greedy/local search algorithms that currently give the best guarantees for submodular maximization.

- advance the theory of heapability of integer sequences and partial orders, along the lines of the rich theory of the longest increasing subsequence problem, by developing and analyzing notions of generalized width of (random) partial orders and the connection with concepts such as interacting particle systems, Young tableaux and Robinson-Schensted type bijections.

A strategic (rather than technical) objective is to bring to Romanian research in Theoretical Computer Science a set of problems, approaches and techniques that are synchronized with current top research in the area, and increase the visibility of Romanian research in top venues in Theoretical Computer Science.

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