Selected Publications

- The Complexity of the Ideal Membership Problem for
Constrained Problems Over the Boolean Domain.
SODA 2019
- High Degree Sum of Squares Proofs,
Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts, SIAM Journal of
Optimization 2020.
- Tight Sum-of-Squares lower bounds for binary
polynomial optimization problems,
ICALP 2016 (track A).
- Sum-Of-Squares hierarchy lower bounds for symmetric
formulations,
Mathematical Programming 2019.
- Semidefinite and linear programming integrality
gaps for scheduling identical machines,
Mathematical Programming 2018.
- On the Hardest Problem Formulations for the 0/1
Lasserre Hierarchy.
Mathematics of Operations Research 2017.
- An unbounded Sum of Squares hierarchy integrality
gap for a polynomially solvable problem,
Mathematical Programming 2017.
- How
to sell
hyperedges: the hyper matching assignment problem SODA 2013.
- Vertex
cover in graphs with locally few colors
ICALP 2011, Information and Computation (ICALP 2011 invited
paper).
- Hardness
of Approximating Flow and Job Shop Scheduling Problems
Journal of the ACM 2011
(FOCS 2008, ICALP 2009).
- Inapproximability
Results for Sparsest Cut, Optimal Linear Arrangement, and
Precedence Constraint Scheduling
SICOMP 2011 (FOCS 2007).
- On
the approximability of the Single-Machine Scheduling with
Precedence Constraints
Mathematics of Operations Research 2011 (APPROX 2006 & IPCO
2007 & FOCS 2007).
- Grouping
techniques for scheduling problems: simpler and faster
Algorithmica 2008.
- Single
machine precedence constrained scheduling is a vertex cover
problem
Algorithmica 2009.
- Effective
neighbourhood functions for the flexible job shop problem
Journal of Scheduling, 2000 [.html]
PC Member
- ICALP (Track A) 2018,
WAOA 2017, COCOON 2017, CIAC 2017, WAOA
2016 (co-chair),
WAOA 2014, WADS 2013, WG 2013, APPROX
2012,
STACS
2012,
WAOA
2011,
MAPSP
2011,
APPROX
2010,
WAOA
2010,
WAOA
2009,
HiPC
2009
PhD Students
Teaching