Theoretical Computer Science Group


STRUCTCOMB,  “Structure and computational difficulty in combinatorial optimization: an interdisciplinary approach” contract

  • CNCS IDEI Grant PN-II-ID-PCE-2011-3-0981
  • Principal investigator: Gabriel Istrate.
  • Starting date: May 1st 2012.
  • Duration: until April 30 2015. April 30 2016. December 31, 2016





  • Project proposal and objectives
  • (Martie 2012, in romanian): Institutul e-Austria angajeaza cercetatori stiintifici (postdoctorali) in matematica-informatică in cadrul proiectului PN-II-ID-PCE-2011-3-0981 “Structure and computational difficulty in combinatorial optimization: an interdisciplinary approach” (data limita: 30 Aprilie 2012)
  • (March 2012, IN ENGLISH): Hiring ads: ANCS and Euraxess (only valid until April 30, 2012)
  • Reports (tar.gz.archive)


collaborating with Eva Kaslik and Mircea Marin.


  • Programs to generate (hard to solve) instances of satisfiability/ILP based on Kneser and Schrijver’s theorems. (Note: SAT instances are in DIMACS-CNF format; for ILP solving one needs GUROBI)


Essentially completed papers, under (re)submission.


Manuscripts in progress

  • Gabriel Istrate, Cosmin Bonchiș, Parameterized complexity of computing power indices in cooperative skill games with agent failures.
  • Gabriel Istrate, Predrag Janičić. ” Locating phase transition in mixture models of constraint satisfaction problems”.
  • Gabriel Istrate, Cosmin Bonchiș. Hammersley’s process with multiple lifelines and a conjecture on decomposing permutations into heapable sequences.
  • Janos Balogh, Cosmin Bonchis, Diana Dinis Gabriel Istrate (title in progress).
  • Gabriel Istrate, Adrian Crăciun, Cosmin Bonchiş Topological obstructions to the colorability of gain graphs
  • Gabriel Istrate, Adrian Crăciun “Parameterized inverse Satisfiability”
  • Gabriel Istrate, Cosmin Bonchiş, Mircea Marin “On the Curvature of Submodular Functions and the Approximability of Minimum Entropy Submodular Set Cover”
  • Gabriel Istrate, Cosmin Bonchis “A greedy approach to low entropy couplings”.
  • Cosmin Bonchiş, Gabriel Istrate “Minimum entropy solutions to assignment problems”
  • Gabriel Istrate, “An accessibility relation on polymatroids and minimum entropy optimization”