Boolean function complexity. Advances and frontiers.
From MaRDI portal
Publication:642463
DOI10.1007/978-3-642-24508-4zbMath1235.94005MaRDI QIDQ642463
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
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
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
Unnamed Item, Unnamed Item, On the Complexity of Multivalued Logic Functions over Some Infinite Basis, Communication Lower Bounds via Critical Block Sensitivity, Formulas versus Circuits for Small Distance Connectivity, Deterministic Communication vs. Partition Number, Extension Complexity of Independent Set Polytopes, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Query-to-Communication Lifting for BPP, On the resolution of the sensitivity conjecture, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS, ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO, On Expressing Majority as a Majority of Majorities, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, On the $AC^0$ Complexity of Subgraph Isomorphism, New bounds for energy complexity of Boolean functions, Rectangles Are Nonnegative Juntas, Non-commutative circuits and the sum-of-squares problem, Separating OR, SUM, and XOR circuits, A note on the size of prenex normal forms, On various nonlinearity measures for Boolean functions, On the read-once property of branching programs and CNFs of bounded treewidth, Zero-information protocols and unambiguity in Arthur-Merlin communication, 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, Lower bounds for tropical circuits and dynamic programs, Limitations of incremental dynamic programming, A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function, Negation-limited formulas, Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity, On the limits of gate elimination, The landscape of communication complexity classes, Upper bounds for the size and the depth of formulae for MOD-functions, Asymptotics of growth for non-monotone complexity of multi-valued logic function systems, Size-treewidth tradeoffs for circuits computing the element distinctness function, Multiplicative complexity of vector valued Boolean functions, The minimum number of negations in circuits for systems of multi-valued functions, On the CNF-complexity of bipartite graphs containing no squares, On the mystery of negations in circuits: structure vs power, Skew circuits of small width, The function-inversion problem: barriers and opportunities, Power of uninitialized qubits in shallow quantum circuits, Exact value of the nonmonotone complexity of Boolean functions, Computing majority by constant depth majority circuits with low fan-in gates, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates, A short proof that the extension complexity of the correlation polytope grows exponentially, Cancellation-free circuits in unbounded and bounded depth, Mining circuit lower bound proofs for meta-algorithms, On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth, Bounds in ontology-based data access via circuit complexity, On compiling structured CNFs to OBDDs, Local bounds for the optimal information ratio of secret sharing schemes, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), The price of query rewriting in ontology-based data access, Alternation, sparsity and sensitivity: bounds and exponential gaps, Circuit lower bounds from learning-theoretic approaches, Tropical Complexity, Sidon Sets, and Dynamic Programming, No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth, Constructive Relationships Between Algebraic Thickness and Normality, Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound, Unnamed Item, Circuit Complexity Meets Ontology-Based Data Access, On Compiling Structured CNFs to OBDDs, A sprouting tree model for random boolean functions
