Krzysztof Sornat

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]



Publications (see also Google Scholar and DBLP)

[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