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

DOI10.4171/OWR/2018/51zbMATH Open1439.00052OpenAlexW4247883467MaRDI QIDQ782965FDOQ782965

Authors:

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

Recommendations

• Complexity theory. Abstracts from the workshop held November 15--21, 2015
• Complexity theory. Abstracts from the workshop held November 11--17, 2012.
• Complexity theory. Abstracts from the workshop held November 15th -- November 21st, 2009
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Complexity theory

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Proceedings of conferences of miscellaneous specific interest (00B25) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Collections of abstracts of lectures (00B05) 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

Cited In (9)

• Complexity theory. Abstracts from the workshop held November 15th -- November 21st, 2009
• Proof complexity and beyond. Abstracts from the workshop held August 13--19, 2017
• Complexity theory. Abstracts from the workshop held November 15--21, 2015
• Complexity theory. Abstracts from the workshop held November 11--17, 2012.
• Contemporary coding theory. Abstracts from the workshop held March 17--23, 2019
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Connections between artificial intelligence and computational complexity and the complexity of graphs
• Computability theory. Abstracts from the workshop held January 7--13, 2018

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782965)