Denis Pankratov

Home | CV | Publications | Teaching | Students

Publications and Preprints

  1. Ali Mohammad Lavasani, Denis Pankratov, Advice Complexity of Online Non-Crossing Matching,
    submitted, [arXiv]

  2. Mahtab Masoori, Lata Narayanan, Denis Pankratov, Renting Servers in the Cloud: The Case of Equal Duration Jobs,
    submitted, [arXiv]

  3. Jurek Czyzowicz, Evangelos Kranakis, Ryan Killick, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, Sunil Shende, Group Evacuation on a Line by Agents with Different Communication Abilities,
    ISAAC 2021, [arXiv]

  4. Hovhannes Harutyunyan, Denis Pankratov, Jesse Racicot, Online Domination: The Value of Getting to Know All your Neighbors,
    MFCS 2021, [arXiv]

  5. Jurek Czyzowicz, Stefan Dobrev, Evangelos Kranakis, Ryan Killick, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, Sunil Shende, Graph Exploration by Energy-Sharing Mobile Agents ,
    SIROCCO 2021, [arXiv]

  6. Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, The Bike Sharing Problem ,
    WALCOM 2021, [arXiv]

  7. Yaqiao Li, Vishnu V. Narayan, Denis Pankratov, Online Coloring and a New Type of Adversary for Online Graph Problems ,
    WAOA 2020, [arXiv]

  8. Allan Borodin, Christodoulos Karavasilis, Denis Pankratov, An Experimental Study of Algorithms for Online Bipartite Matching ,
    ACM J. Exp. Algorithmics 25:1-37, [arXiv]

  9. Joan Boyar, Kim S. Larsen, Denis Pankratov, Advice Complexity of Priority Algorithms ,
    submitted, [arXiv]

  10. Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, Exploration of Higher Dimensional Grids by Finite State Machines ,
    ICALP 2019, [arXiv]

  11. Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov, Advice Complexity of Priority Algorithms ,
    WAOA 2018, Theory of Comput. Syst. J. 2020, [arXiv]

  12. Allan Borodin, Christodoulos Karavasilis, Denis Pankratov, Greedy Bipartite Matching in Random Type Poisson Arrival Model ,
    APPROX/RANDOM 2018, [arXiv]

  13. Paul Beame, Noah Fleming, Russel Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere, Stabbing Planes ,
    ITCS 2018, [arXiv]

  14. Allan Borodin, Denis Pankratov, Amirali Salehi-Abari, A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Variant,
    SOSA 2018, Theory of Comput. Syst. J. 2019, [arXiv]

  15. Allan Borodin, Denis Pankratov, Amirali Salehi-Abari, On Conceptually Simple Algorithms for Variants of Online Bipartite Matching,
    WAOA 2017, invited to special issue, [arXiv]

  16. Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere, Random CNFs are Hard for Cutting Planes,
    FOCS 2017, accepted to JACM, [arXiv]

  17. Denis Pankratov, Communication Complexity and Information Complexity,
    PhD Dissertation, [local]

  18. Laszlo Babai, Denis Pankratov, There are no zero-hard problems in multiparty communication complexity,
    accepted to Chicago Journal of Theoretical Computer Science, [local]

  19. Denis Pankratov, On the Power of Feedback in Interactive Channels,
    preprint, [local]

  20. Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein, Information lower bounds via self-reducibility,
    CSR 2013, Theory of Comput. Syst. J. 2016, [local]

  21. Denis Pankratov, Direct Sum Questions in Classical Communication Complexity,
    Master's Thesis, [local]

  22. Pooya Hatami, Raghav Kulkarni, Denis Pankratov, Variations on the Sensitivity Conjecture,
    Theory of Computing Library, Graduate Surveys Number 4 (2011), [ToC]

  23. Denis Pankratov, Allan Borodin, On the Relative Merits of Simple Local Search Methods for the MAX-SAT Problem,
    SAT 2010, [local]

  24. Alex Varshavsky, Denis Pankratov, John Krumm, Eyal de Lara, Calibree: Calibration-free Localization using Relative Distance Estimations,
    Pervasive 2008, [local]