Krzysztof Sornat
Currently I am a Postdoctoral Fellow at
MIT CSAIL,
hosted by
Virginia Vassilevska Williams.
I work on fine-grained and parameterized complexity of computational problems from social choice theory.
This is my previous homepage---updated when I was a PhD student at University of Wrocław. My current homepage can be found at
www.mit.edu/~sornat.
E-mail: sornat@mit.edu
Research experience
Current position:
(2020.09--2021.02) Postdoctoral Fellow (postdoc) at
MIT, Cambridge CA, USA,
hosted by
Virginia Vassilevska Williams.
Previous positions:
(2020.01--2020.08) Postdoctoral student (postdoc) at
Ben-Gurion University, Israel,
hosted by
Nimrod Talmon.
(2018.05--2018.10) Researcher (postdoc) at
IDSIA, Switzerland,
hosted by
Fabrizio Grandoni.
(2013.10--2019.09) PhD student at
University of Wrocław, Poland
in the Combinatorial Optimization Group,
under the supervision of Jarosław Byrka.
Longer research visits:
(2019.12) a visiting researcher at
Oxford University, UK,
hosted by
Edith Elkind.
(2016.02--2016.06) research internship at
University of Warsaw, Poland,
hosted by
Łukasz Kowalik.
(2015.09--2015.11) research internship at
AUEB, Grecce,
hosted by
Evangelos Markakis.
Research interests
approximation algorithms, parameterized algorithms, linear programming relaxations and rounding procedures,
clustering problems, network design, computational social choice, multiwinner elections, participatory budgeting
PhD thesis
Krzysztof Sornat:
Approximation Algorithms for Multiwinner Elections and Clustering Problems, University of Wrocław, 2019.
[PhD thesis]
Defended on October 10th 2019. [slides]
PhD advisor: Jarosław Byrka (University of Wrocław, Poland)
Reviewers:
Piotr Sankowski (University of Warsaw, Poland)
[review],
Ola Svensson (EPFL, Switzerland)
[review]
[11] Pallavi Jain, Krzysztof Sornat, Nimrod Talmon:
Preserving Consistency for Liquid Knapsack Voting.
[AAMAS 2021 extended abstract (coming soon)]
[ArXiv full version (coming soon)]
[10] Pallavi Jain, Krzysztof Sornat, Nimrod Talmon, Meirav Zehavi:
Participatory Budgeting with Project Groups.
[ArXiv full version]
[9] Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski, Krzysztof Sornat:
Tight Approximation for Proportional Approval Voting.
[IJCAI 2020]
[ArXiv full version (coming soon)]
[8] Pallavi Jain, Krzysztof Sornat, Nimrod Talmon:
Participatory Budgeting with Project Interactions.
[IJCAI 2020]
[ArXiv full version (coming soon)]
[7] Waldo Gálvez, Fabrizio Grandoni, Afrouz Jabal Ameli, Krzysztof Sornat:
On the Cycle Augmentation Problem: Hardness and Approximation Algorithms.
[WAOA 2019]
[ArXiv full version (coming soon)]
[6] Piotr Faliszewski, Pasin Manurangsi, Krzysztof Sornat:
Approximation and Hardness of Shift-Bribery.
[AAAI 2019]
[ArXiv full version]
[5] Jarosław Byrka, Piotr Skowron, Krzysztof Sornat:
Proportional Approval Voting, Harmonic k-Median, and Negative Association.
[ICALP 2018]
[ArXiv full version]
Also presented at ISMP 2018 and appeared as a poster in STOC 2018, WINE 2018, AAAI 2019 and HALG 2019.
[4] Jarosław Byrka, Krzysztof Sornat, Joachim Spoerhase:
Constant-Factor Approximation for Ordered k-Median.
[STOC 2018]
[ArXiv full version]
Also presented at FND 2018, ISMP 2018 and the FIT 2019 workshop, and appeared as a poster in HALG 2018.
[3] Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat:
Approximation and Parameterized Complexity of Minimax Approval Voting.
[Journal of Artificial Intelligence Research]
[AAAI 2017]
[ArXiv full version]
Also presented at the EXPLORE@AAMAS 2017 and PAAW 2018 workshops and appeared as a poster in a few workshops.
[2] Georgios Amanatidis, Evangelos Markakis, Krzysztof Sornat:
Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results.
[MFCS 2016]
[ArXiv full version]
Also presented at the AGT@IJCAI 2016 workshop.
[1] Jarosław Byrka, Krzysztof Sornat:
PTAS for Minimax Approval Voting.
[WINE 2014]
[ArXiv full version]
Also presented at the FIT 2015 workshop.
Research grants
NCN ETIUDA 6
(2018.10--2020.09) Principal investigator in the National Science Center, Poland grant no. 2018/28/T/ST6/00366 entitled "Application of algorithmic techniques in solving social and economic issues". Budget 25,000 EUR.
NCN PRELUDIUM 9
(2016.03--2019.02) Principal investigator in the National Science Center, Poland grant no. 2015/17/N/ST6/03684 entitled "Application of modern algorithmic methods for solving NP-hard clustering problems". Budget 35,000 EUR.
Honors
START 2019 scholarship of the Foundation for Polish Science (FNP) for young, talented researchers
[list of laureates]
[Radio Wrocław interview (Polish)]
[SciencePR article (Polish)]
[wroclaw.pl article (Polish)]
Professional service
Program Committee member: EUMAS 2021, IJCAI 2021 (Senior PC), AAAI 2021, AAMAS 2021.
Reviewer for journals:
Artificial Intelligence (2021), Autonomous Agents and Multi-Agent Systems (2020), Journal of Artificial Intelligence Research (2020), Information Processing Letters (2018), Journal of Combinatorial Optimization (2018), SIAM Journal on Computing (2017), Algorithmica (2017).
Reviewer for conferences:
STACS 2021, SODA 2021, IPEC 2020, COCOON 2020, MFCS 2020, ESA 2020 (x2), ICALP 2020, IJCAI 2020 (x2), AAMAS 2020 (x2), ECAI 2020, WAOA 2019, ICALP 2019, COCOON 2019, SODA 2019, COCOON 2018, CIAC 2017, MFCS 2016, FUN 2016 (x2), MFCS 2015.
last update of the website: January 15th 2021