Liana Khazaliya

Since August 2022, I am a PhD student at TU Wien
supervised by Robert Ganian, and co-supervised by Martin Nöllenburg.

Publications

The Computational Complexity of Positive Non-Clashing Teaching in Graphs
with Robert Ganian, Fionn Mc Inerney, Mathis Rocton. ICLR 2025

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
with Florent Foucaud, Esther Galby, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. STACS 2025

Crossing Number is NP-hard for Constant Path-width (and Tree-width)
with Petr Hliněný. ISAAC 2024

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
with Florent Foucaud, Esther Galby, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. ICALP 2024

The st-Planar Edge Completion Problem is Fixed-Parameter Tractable
with Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov. ISAAC 2023

Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
with Robert Ganian, Kirill Simonov. IPEC 2023

Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
with Bart M.P. Jansen, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov. GD 2023

Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
with Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, Martin Nöllenburg. SoCG 2023
Journal of Computational Geometry (JoCG), Vol. 15 No. 2 (2024)

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
with Esther Galby, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. MFCS 2022
SIAM Journal on Discrete Mathematics (SIDMA), Vol. 37, Iss. 4 (2023)

[DBLP] [Google Scholar]

---

Talks

The Computational Complexity of Positive Non-Clashing Teaching in Graphs

• ICLR 2025, Singapore EXPO [poster]

Crossing Number is NP-hard for Constant Path-width (and Tree-width)

• TCS Seminar, National Institute of Informatics, Tokyo, Japan [slides]
• ISAAC 2024, Sydney, Australia [slides]

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover

• Research Seminar of the ALGO group, TU Eindhoven, The Netherlands [slides]
• ICALP 2024, Tallinn, Estonia [slides]
• GROW 2024, Cottbus, Germany [slides]

Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth

• GD 2023, Palermo, Italy [slides]
• Seminar on Foundations of Computing, Masaryk University, Brno, Czech Republic [slides]
• Research Seminar of the Algorithm Engineering group, Hasso-Plattner-Institut, Potsdam, Germany [slides]

Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable

• contributed talk at IGAFIT Highlights of Algorithms (HALG), Prague, Czech Republic [poster]
• contributed talk at 10th SCGT, Kranjska Gora, Slovenia [slides]

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

• MFCS 2022, Vienna, Austria [slides]

---

Reviewing

Conferences: ICALP 2025, WALCOM 2025, ESA 2024, SoCG 2024, STACS 2024, GD 2023, SOFSEM 2022, IPEC 2022
Journals: SIAM Journal on Discrete Mathematics, Journal of Artificial Intelligence

---

Education

• PhD student, Algorithms and Complexity Group
  TU Wien, Vienna, Austria
  Since August 2022
  Guild Leader: Robert Ganian
• M.Sc., Department of Mathematics and Computer Science
  Saint Petersburg University, Saint Petersburg, Russia
  September 2020 – June 2022
• B.Sc. in Minsk, Belarus
  September 2016 – June 2020
• Computer Science Center
  Saint Petersburg, Russia
  September 2021 – May 2022

---

Work experience

• Assistant
  Fall and Winter Semesters 2021–⁠2022
  Seminars on algorithms for first-year BSc students
  Saint Petersburg State University
• System Analyst
  from March 2020 to March 2021
  “HiQo Solutions”
• Math tutor, Coordinator
  from December 2016 to June 2022
  Preparing school students for mathematical competitions (olympiads, tournaments, etc.)

---

Other

• Certified in Rope Access Services (industrial climbing);
• Long-distance cyclist;
• Bouldering and sport climbing fan;
• Juggler, unicyclist, slackline enjoyer;
• Kayaking;
• Minesweeper [Expert]: 80 sec.

Last updated on 24 January 2024