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

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

Review text

Summary: Computational Complexity Theory is the mathematical study of the intrinsic power and limitations of computational resources like time, space, or randomness. The current workshop focused on recent developments in various sub-areas including arithmetic complexity, Boolean complexity, communication complexity, cryptography, probabilistic proof systems, pseudorandomness, and quantum computation. Many of the developments are related to diverse mathematical fields such as algebraic geometry, combinatorial number theory, probability theory, representation theory, and the theory of error-correcting codes.

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)

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

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)