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

DOI10.4171/OWR/2018/51MaRDI QIDQ782965zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)
• Connections between artificial intelligence and computational complexity and the complexity of graphs
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• 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)