4 citations · 12 across the 25 of their papers we have counts for
4 papers · 1 filter
The Complexity of Constrained Min-Max Optimization
Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis
Despite its important applications in Machine Learning, min-max optimization of nonconvex-nonconcave objectives remains elusive. Not only are there no known first-order methods con…
A Topological Characterization of Modulo- Arguments and Implications for Necklace Splitting
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki +1
The classes PPA- have attracted attention lately, because they are the main candidates for capturing the complexity of Necklace Splitting with thieves, for prime . Howeve…
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
Mika Göös, Pritish Kamath, Katerina Sotiraki +1
We study the search problem class defined as a modulo- analog of the well-known class introduced by Papadim…
PPP-Completeness with Connections to Cryptography
Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis
Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant…