Boolean function complexity. Advances and frontiers.

DOI10.1007/978-3-642-24508-4zbMath1235.94005MaRDI QIDQ642463

Stasys P. Jukna

Publication date: 26 October 2011

Published in: Algorithms and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-24508-4

zbMATH Keywords

Fourier transform; lower bounds; cutting planes; graph entropy; decision trees; Boolean function; threshold functions; circuit complexity; switching network; expanders; Markov's theorem; Barrington's theorem; Chvátal rank; distributional complexity; Fischer's theorem; greedy bounds; Kannan's lower bound; Khrapchenko's theorem; large-depth circuits; Nechiporuk's theorem; pseudo-random generators; span programs; Tseitin formulas; Williams' lower bound

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

94-02: Research exposition (monographs, survey articles) pertaining to information and communication theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03F20: Complexity of proofs

Related Items

Non-commutative circuits and the sum-of-squares problem, Cutting planes cannot approximate some integer programs, Clique problem, cutting plane proofs and communication complexity, Upper bounds for the formula size of symmetric Boolean functions, Random arithmetic formulas can be reconstructed efficiently, On the CNF-complexity of bipartite graphs containing no squares, A short proof that the extension complexity of the correlation polytope grows exponentially, The price of query rewriting in ontology-based data access