Boolean function complexity. Advances and frontiers.

DOI10.1007/978-3-642-24508-4zbMath1235.94005OpenAlexW2490907619MaRDI 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

zbMATH Keywords

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items

Random $ \Theta (\log n) $ -CNFs are Hard for Cutting Planes, On (simple) decision tree rank, Algorithms and lower bounds for comparator circuits from shrinkage, Improvement of nonmonotone complexity estimates of $k$-valued logic functions, Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic, On the extension complexity of polytopes separating subsets of the Boolean cube, Communication and information complexity, String Matching: Communication, Circuits, and Learning., ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS, ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO, 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, Regular expression length via arithmetic formula complexity, On Expressing Majority as a Majority of Majorities, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, MaxSAT Resolution and Subcube Sums, Separating OR, SUM, and XOR circuits, A note on the size of prenex normal forms, Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity, Expander-based cryptography meets natural proofs, On various nonlinearity measures for Boolean functions, On the Decision Tree Complexity of Threshold Functions, What Circuit Classes Can Be Learned with Non-Trivial Savings?, On the limits of gate elimination, Alternation, sparsity and sensitivity: bounds and exponential gaps, On the read-once property of branching programs and CNFs of bounded treewidth, Unnamed Item, Circuit lower bounds from learning-theoretic approaches, Approximate Degree in Classical and Quantum Computing, A sprouting tree model for random boolean functions, 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, The landscape of communication complexity classes, Zero-information protocols and unambiguity in Arthur-Merlin communication, Improved bounds on the an-complexity of $O(1)$-linear functions, Quadratic lower bounds for algebraic branching programs and formulas, Circuit Complexity Meets Ontology-Based Data Access, On Compiling Structured CNFs to OBDDs, Deterministic Communication vs. Partition Number, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Skew circuits of small width, The function-inversion problem: barriers and opportunities, On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth, Upper bounds for the size and the depth of formulae for MOD-functions, Bounds in ontology-based data access via circuit complexity, On compiling structured CNFs to OBDDs, Partial order games, No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth, Nearest neighbor representations of Boolean functions, Lower bounds for Boolean circuits of bounded negation width, Constructive Relationships Between Algebraic Thickness and Normality, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, Worst-Case to Average-Case Reductions for Subclasses of P, On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions, Local bounds for the optimal information ratio of secret sharing schemes, Asymptotics of growth for non-monotone complexity of multi-valued logic function systems, Unnamed Item, On the CNF-complexity of bipartite graphs containing no squares, Query-to-communication lifting for $\mathsf{P}^{\mathsf{NP}}$, Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound, On the binary and Boolean rank of regular matrices, Size-treewidth tradeoffs for circuits computing the element distinctness function, Query-to-Communication Lifting for BPP, Unnamed Item, Extension Complexity of Independent Set Polytopes, Deciding FO-definability of regular languages, Multiplicative complexity of vector valued Boolean functions, Grafting key trees: efficient key management for overlapping groups, On the resolution of the sensitivity conjecture, 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, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, Power of uninitialized qubits in shallow quantum circuits, Unnamed Item, Unnamed Item, The price of query rewriting in ontology-based data access, Random arithmetic formulas can be reconstructed efficiently, Lower bounds for tropical circuits and dynamic programs, A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function, The minimum number of negations in circuits for systems of multi-valued functions, Limitations of incremental dynamic programming, On the mystery of negations in circuits: structure vs power, Unnamed Item, Unnamed Item, Unnamed Item, Negation-limited formulas, Formula complexity of a linear function in a $k$-ary basis, Nondeterministic and randomized Boolean hierarchies in communication complexity, Counting the number of perfect matchings, and generalized decision trees, Unnamed Item, Unnamed Item, Unnamed Item, Adventures in monotone complexity and TFNP, Lifting Theorems for Equality, Lower Bounds for DeMorgan Circuits of Bounded Negation Width, The Orthogonal Vectors Conjecture for Branching Programs and Formulas, Hardness magnification near state-of-the-art lower bounds, Algorithms and lower bounds for de morgan formulas of low-communication leaf gates, Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs, Exact value of the nonmonotone complexity of Boolean functions, Tropical Complexity, Sidon Sets, and Dynamic Programming, Computing majority by constant depth majority circuits with low fan-in gates, Unnamed Item, Unnamed Item, Proving that $\mathrm{prBPP}=\mathrm{prP}$ is as hard as proving that ``almost NP is not contained in P/poly, Bounded-depth Frege complexity of Tseitin formulas for all graphs, On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates, On the decision tree complexity of threshold functions, A short proof that the extension complexity of the correlation polytope grows exponentially, Unnamed Item, Cancellation-free circuits in unbounded and bounded depth, PAC-learning gains of Turing machines over circuits and neural networks, Mining circuit lower bound proofs for meta-algorithms, On separation between the degree of a Boolean function and the block sensitivity