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-011 | 17th February 2025
Oded Goldreich, Roei Tell

Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems

Pseudodeterministic algorithms are probabilistic algorithms that solve search problems but do so by always providing the same (``canonical'') solution to a given instance, except with small probability.
While the complexity theoretic implications of pseudodeterministic algorithms were explored in the past, we suggest to conduct this exploration within the framework ... more >>>


TR25-010 | 11th February 2025
Marshall Ball, Lijie Chen, Roei Tell

Towards Free Lunch Derandomization from Necessary Assumptions (and OWFs)

The question of optimal derandomization, introduced by Doron et. al (JACM 2022), garnered significant recent attention. Works in recent years showed conditional superfast derandomization algorithms, as well as conditional impossibility results, and barriers for obtaining superfast derandomization using certain black-box techniques.

Of particular interest is the extreme high-end, which ... more >>>


TR25-009 | 7th February 2025
Marco Aldi, Sevag Gharibian, Dorian Rudolph

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint