White-box vs. black-box complexity of search problems: Ramsey and graph property testing
Ramsey theory assures us that in any graph there is a clique or independent set of a certain
size, roughly logarithmic in the graph size. But how difficult is it to find the clique or …
size, roughly logarithmic in the graph size. But how difficult is it to find the clique or …
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
AR Choudhuri, P Hubáček, C Kamath… - Proceedings of the 51st …, 2019 - dl.acm.org
The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive
argument, by replacing the verifier with a cryptographic hash function that is applied to the …
argument, by replacing the verifier with a cryptographic hash function that is applied to the …
The complexity of splitting necklaces and bisecting ham sandwiches
A Filos-Ratsikas, PW Goldberg - Proceedings of the 51st Annual ACM …, 2019 - dl.acm.org
We resolve the computational complexity of two problems known as Necklace Splitting and
Discrete Ham Sandwich, showing that they are PPA-complete. For Necklace Splitting, this …
Discrete Ham Sandwich, showing that they are PPA-complete. For Necklace Splitting, this …
Consensus halving is PPA-complete
A Filos-Ratsikas, PW Goldberg - Proceedings of the 50th Annual ACM …, 2018 - dl.acm.org
We show that the computational problem Consensus Halving is PPA-Complete, the first PPA-
Completeness result for a problem whose definition does not involve an explicit circuit. We …
Completeness result for a problem whose definition does not involve an explicit circuit. We …
[PDF][PDF] Total functions in the polynomial hierarchy
We identify several genres of search problems beyond NP for which existence of solutions is
guaranteed. One class that seems especially rich in such problems is PEPP (for" polynomial …
guaranteed. One class that seems especially rich in such problems is PEPP (for" polynomial …
Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions
R Shaltiel, J Silbak - Proceedings of the 56th Annual ACM Symposium …, 2024 - dl.acm.org
Codes for poly-size circuits: Guruswami and Smith (J. ACM 2016) considered codes for
channels that are poly-size circuits which modify at most ap-fraction of the bits of the …
channels that are poly-size circuits which modify at most ap-fraction of the bits of the …
PPP-completeness with connections to cryptography
K Sotiraki, M Zampetakis… - 2018 IEEE 59th Annual …, 2018 - ieeexplore.ieee.org
Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound
connections to the complexity of the fundamental cryptographic primitives: collision-resistant …
connections to the complexity of the fundamental cryptographic primitives: collision-resistant …
Non-malleable codes with optimal rate for poly-size circuits
We give an explicit construction of non-malleable codes with rate 1-o (1) for the tampering
class of poly-size circuits. This rate is optimal, and improves upon the previous explicit …
class of poly-size circuits. This rate is optimal, and improves upon the previous explicit …
Towards a unified complexity theory of total functions
PW Goldberg, CH Papadimitriou - Journal of Computer and System …, 2018 - Elsevier
The class TFNP, of NP search problems where all instances have solutions, appears not to
have complete problems. However, TFNP contains various syntactic subclasses and …
have complete problems. However, TFNP contains various syntactic subclasses and …
Statistically sender-private OT from LPN and derandomization
N Bitansky, S Freizeit - Annual International Cryptology Conference, 2022 - Springer
We construct a two-message oblivious transfer protocol with statistical sender privacy (SSP
OT) based on the Learning Parity with Noise (LPN) Assumption and a standard Nisan …
OT) based on the Learning Parity with Noise (LPN) Assumption and a standard Nisan …