Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-070 | 2nd June 2025
Halley Goldberg, Valentine Kabanets

Witness Encryption and NP-hardness of Learning

We study connections between two fundamental questions from computer science theory. (1) Is witness encryption in the sense of Garg et al. (2013) possible for NP? That is, given an instance $x$ of an NP-complete language $L$, can one encrypt a secret message with security contingent on the ability to ... more >>>


TR25-069 | 30th May 2025
Noah Fleming, Christophe Marciot, Deniz imrek

Provably Total Functions in the Polynomial Hierarchy

TFNP studies the complexity of total, verifiable search problems, and represents the first layer of the total function polynomial hierarchy (TFPH). Recently, problems in higher levels of the TFPH have gained significant attention, partly due to their close connection to circuit lower bounds. However, very little is known about the ... more >>>


TR25-068 | 23rd May 2025
Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, Ilya Volkovich

Communication Complexity of Equality and Error Correcting Codes

We study the randomized communication complexity of the equality function in the public-coin model. Although the communication complexity of this function is known to be low in the setting where error probability is constant and a large number of random bits are available to players, the complexity grows if the ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint