Boolean function complexity. Advances and frontiers.

DOI10.1007/978-3-642-24508-4zbMATH Open1235.94005OpenAlexW2490907619MaRDI QIDQ642463FDOQ642463

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

Recommendations

scientific article; zbMATH DE number 4012495
scientific article; zbMATH DE number 1161568
scientific article; zbMATH DE number 953683
scientific article; zbMATH DE number 194333
scientific article; zbMATH DE number 42045

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)

Cited In (only showing first 100 items - show all)

Mining circuit lower bound proofs for meta-algorithms
Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
Title not available (Why is that?)
Title not available (Why is that?)
The computational complexity of equivalence and isomorphism problems
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
On compiling structured CNFs to OBDDs
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
On the resolution of the sensitivity conjecture
Lower bounds for tropical circuits and dynamic programs
The price of query rewriting in ontology-based data access
A note on the size of prenex normal forms
Separating OR, SUM, and XOR circuits
On various nonlinearity measures for Boolean functions
Circuit complexity meets ontology-based data access
Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
Size-treewidth tradeoffs for circuits computing the element distinctness function
Algorithms and lower bounds for comparator circuits from shrinkage
Rectangles are nonnegative juntas
Testing \(k\)-monotonicity
On the mystery of negations in circuits: structure vs power
On the limits of gate elimination
Negation-limited formulas
Stabbing planes
On the read-once property of branching programs and CNFs of bounded treewidth
ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
Cutting planes cannot approximate some integer programs
Monotone circuit lower bounds from resolution
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
Formula complexity of a linear function in a \(k\)-ary basis
The landscape of communication complexity classes
Constructive relationships between algebraic thickness and normality
Clique problem, cutting plane proofs and communication complexity
Title not available (Why is that?)
Nondeterministic and randomized Boolean hierarchies in communication complexity
Counting the number of perfect matchings, and generalized decision trees
On compiling structured CNFs to OBDDs
Cancellation-free circuits in unbounded and bounded depth
Non-commutative circuits and the sum-of-squares problem
On the complexity of multivalued logic functions over some infinite basis
Upper bounds for the formula size of symmetric Boolean functions
On the CNF-complexity of bipartite graphs containing no squares
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
Lower bounds for Boolean circuits of bounded negation width
Upper bounds for the size and the depth of formulae for MOD-functions
Zero-information protocols and unambiguity in Arthur-Merlin communication
Random arithmetic formulas can be reconstructed efficiently
Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
No small nondeterministic read-once branching programs for CNFs of bounded treewidth
The minimum number of negations in circuits for systems of multi-valued functions
A short proof that the extension complexity of the correlation polytope grows exponentially
Multiplicative complexity of vector valued Boolean functions
Extension complexity of independent set polytopes
On the binary and Boolean rank of regular matrices
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
Hardness magnification near state-of-the-art lower bounds
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
Adventures in monotone complexity and TFNP
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
Lower Bounds for DeMorgan Circuits of Bounded Negation Width
Recent progress in the Boolean domain
Title not available (Why is that?)
On the extension complexity of polytopes separating subsets of the Boolean cube
Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
New bounds for energy complexity of Boolean functions
A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
Limitations of incremental dynamic programming
Lifting Theorems for Equality
Local bounds for the optimal information ratio of secret sharing schemes
A sprouting tree model for random boolean functions
Communication lower bounds via critical block sensitivity
Deciding FO-definability of regular languages
Computing majority by constant depth majority circuits with low fan-in gates
Title not available (Why is that?)
Complexity of quantum circuits via sensitivity, magic, and coherence
Circuit complexity before the dawn of the new millennium
Tropical Circuit Complexity
PAC-learning gains of Turing machines over circuits and neural networks
Power of uninitialized qubits in shallow quantum circuits
Worst-Case to Average-Case Reductions for Subclasses of P
On the hardness of approximate and exact (bichromatic) maximum inner product
On separation between the degree of a Boolean function and the block sensitivity
Expander-based cryptography meets natural proofs
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Monotone classes beyond VNP
Regular expression length via arithmetic formula complexity
Title not available (Why is that?)
MaxSAT Resolution and Subcube Sums
String Matching: Communication, Circuits, and Learning.
On (simple) decision tree rank
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
Alternation, sparsity and sensitivity: bounds and exponential gaps
Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
Title not available (Why is that?)
Book review of: S. Jukna, Boolean function complexity. Advances and frontiers.
A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
One-tape Turing machine and branching program lower bounds for MCSP
Depth-3 circuits for inner product
On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q642463)