Complexity theory. Abstracts from the workshop held November 11--17, 2018

DOI10.4171/OWR/2018/51zbMath1439.00052OpenAlexW4247883467MaRDI QIDQ782965

No author found.

Publication date: 29 July 2020

Published in: Oberwolfach Reports (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4171/owr/2018/51

Mathematics Subject Classification ID

Proceedings of conferences of miscellaneous specific interest (00B25) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Collections of abstracts of lectures (00B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of computing (68Q01)

Cites Work

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP

This page was built for publication: Complexity theory. Abstracts from the workshop held November 11--17, 2018