Boolean function complexity. Advances and frontiers.

DOI10.1007/978-3-642-24508-4zbMath1235.94005OpenAlexW2490907619MaRDI 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 transformlower boundscutting planesgraph entropydecision treesBoolean functionthreshold functionscircuit complexityswitching networkexpandersMarkov's theoremBarrington's theoremChvátal rankdistributional complexityFischer's theoremgreedy boundsKannan's lower boundKhrapchenko's theoremlarge-depth circuitsNechiporuk's theorempseudo-random generatorsspan programsTseitin formulasWilliams' lower bound

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 (only showing first 100 items - show all)

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 ⋮ Unnamed Item ⋮ 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 ⋮ 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

This page was built for publication: Boolean function complexity. Advances and frontiers.