Piotr Krysta

Research highlights

My research interests are in theoretical computer science with an emphasis on algorithmic mechanism design, algorithmic game theory, combinatorial and continuous optimization, mathematical programming, approximation algorithms, randomized algorithms and probabilistic analysis, distributed algorithms, and their applications in computational economics, blockchains, computational chemistry, Artificial Intelligence and Machine Learning.

Newest research papers

Below are some of my new papers that were accepted for publication:

• Kiarash Banihashem, Mohammad T. Hajiaghayi, Piotr Krysta, Suho Shin, "Delegated Choice with Combinatorial Constraints", accepted for publication at 26th ACM Conference on Economics and Computation (EC'25), 2025. NEW!!!

• Mohammad T. Hajiaghayi, Piotr Krysta, Mohammad Mahdavi, Suho Shin, "Delegation with Costly Inspection", accepted for publication at 26th ACM Conference on Economics and Computation (EC'25), 2025. NEW!!!

• Kiarash Banihashem, Mohammad T. Hajiaghayi, Dariusz Kowalski, Piotr Krysta, Danny Mittal, Jan Olkowski, "Beating Competitive Ratio 4 for Graphic Matroid Secretary", accepted for publication at 33rd Annual European Symposium on Algorithms (ESA'25), 2025. NEW!!!

• Dariusz Kowalski, Piotr Krysta, Shay Kutten, "What is the minimum number of random bits required for computability and efficiency in anonymous networks?", accepted for publication at 29th International Conference on Randomization and Computation (RANDOM'25), 2025. NEW!!!

Approximation algorithms for hard optimization problems

Below is the full and comprehensive treatment (60 pages) of approximability of one of the most fundamental NP-hard graph optimization problems -- maximum size independent set (MIS) problem in bounded degree graphs. In this paper we solve a classic open problem from 1995 by designing provably best greedy approximation algorithm for MIS on subcubic graphs. Our analysis of the greedy method is state-of-the-art and implies simple analysis for the greedy approximation ratios for MIS on bounded degree graphs along with related impossibility and hardness results:

• Piotr Krysta, Mathieu Mari and Nan Zhi, “Ultimate greedy approximation of independent sets in subcubic graphs”. Algorithmica, 86(11): pp. 3518-3578, 2024.  NEW!!! Preliminary version at ACM-SIAM SODA 2020.

Stochastic optimization & algorithmic mechanism design

Suppose that we are given a stream of n numbers chosen and labelled by an adversary. We have designed an algorithm that provably uses the smallest amount of randomness to decide the best order to inspect these numbers to choose k (< n) among them whose sum has the best possible competitive ratio (with respect to the sum of k largest numbers in the whole stream). This is the fundamental free-order multiple-choice secretary problem:

• M. T. Hajiaghayi, D. Kowalski, P. Krysta and J. Olkowski, Online Sampling and Decision Making with Low Entropy, Proceedings 33rd International Joint Conference on Artificial Intelligence (IJCAI), 2024. NEW!!!

We have solved an important open problems in stochastic optimization, namely proving that any algorithm for the Prophet Inequality problem with general combinatorial feasibility constraints can be turned into a pricing-based (poste-price) algorithm for the same problem, preserving the expected competitive ratio and the distribution over the outputs of the original algorithm:

• K. Banihashem, M. T. Hajiaghayi, D. Kowalski, P. Krysta and J. Olkowski, Power of Posted-price Mechanisms for Prophet Inequalities, Proceedings 35th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024. NEW!!!

Theory of adversarial equilibria

We have introduced recently a novel concept of Adversarial Equilibrium, which is motivated by a notion of Nash Equilibrium and Pareto Optimality from Game Theory and a notion of an Adversary from Distributed Computing. We design non-adaptive algorithms and prove that they are Adversarial Equilibria for the Contention Resolution problem:

• G. Chionas, B. Chlebus, D. Kowalski and P. Krysta, Adversarial Contention Resolution Games, Proceedings 32nd International Joint Conference on Artificial Intelligence (IJCAI), 2023.

We considerably generalize this model to Combinatorial Group Testing (CGT) games and design more demanding adaptive algorithms which are Adversarial Equilibria for the CGT problem:

• G. Chionas, D. Kowalski and P. Krysta, Combinatorial Group Testing with Selfish Agents, Proceedings 37th International Conference on Neural Information Processing Systems (NeurIPS), 2023. 

Continuous and discrete optimization in chemistry

I am a computer science co-investigator in the Material Innovation Factory (University of Liverpool), working in a multidisciplinary team of Chemists and Computer Scientists in the project on continuous optimization algorithms for Crystal Structure Prediction (CSP) of solid materials on the atomic level. Here is our recent paper in this area, where we design algorithms for CSP based on integer quadratic programming, with provable optimality guarantees:

• V. Gusev, D. Adamson, A. Deligkas, D. Antypov, C. Collins, P. Krysta, I. Potapov, G. Darling, W. Dyer, P. Spirakis and M. Rosseinsky

    Optimality guarantees for crystal structure prediction, Nature, vol. 619, pp. 68–72, 2023.

In a recently concluded PhD project, for which I served as the primary supervisor, Antonia Tsili and our team have conducted a thorough theoretical and experimental, including full implementation, analysis of first-order optimization methods for the relaxation problem in crystal structure prediction:

• A. Tsili, M.S. Dyer, V.V. Gusev, P. Krysta, and R. Savani, “First Order Methods for Geometric Optimization of Crystals: Theoretical Deriva- tions”. Advanced Theory and Simulations, 7(7), July 2024. NEW!!!

• A. Tsili, M.S. Dyer, V.V. Gusev, P. Krysta, and R. Savani. “First Order Methods for Geometric Optimization of Crystals: Experimental Analysis”. Advanced Theory and Simulations, 7(8), August 2024. NEW!!!

Algorithms and mechanisms for blockchain

Maximal Extractable Value (MEV) has emerged as a new frontier in the design of blockchain systems. We propose to make the MEV extraction rate part of the protocol design space. We have designed a dynamic mechanism which updates the MEV extraction rate with the goal of stabilizing it at a target value. We analyse the evolution of this dynamic mechanism under various market conditions and provide formal guarantees about its long-term performance. The main take-away from our work is that the proposed system exhibits desirable behavior (near-optimal performance) even when it operates in out of equilibrium conditions.

• P. Braga, G. Chionas, P. Krysta, S. Leonardos, G. Piliouras and C. Ventre, Who gets the Maximal Extractable Value? A Dynamic Sharing Blockchain Mechanism, Extended Abstract in the Proceedings 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2024. NEW!!!

• P. Braga, G. Chionas, P. Krysta, S. Leonardos, G. Piliouras, C. Ventre, “MEV Sharing with Dynamic Extraction Rates”. In the Proceedings ACM CCS Workshop on Decentralized Finance and Security (DeFi’24), 2024. NEW!!!

Contact: pkrysta at augusta.edu