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)

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
Deterministic communication vs. partition number
Query-to-communication lifting for BPP
Flipping out with many flips: hardness of testing \(k\)-monotonicity
Improved bounds on the an-complexity of \(O(1)\)-linear functions
Hardness magnification near state-of-the-art lower bounds
CNF encodings of symmetric functions
Partial order games
Formulas versus Circuits for Small Distance Connectivity
Communication and information complexity
Energy and output patterns in Boolean circuits
Computationally hard problems for logic programs under answer set semantics
Cutting planes width and the complexity of graph isomorphism refutations
Title not available (Why is that?)
On the Decision Tree Complexity of Threshold Functions
Title not available (Why is that?)
Circuit lower bounds from learning-theoretic approaches
Skew circuits of small width
The function-inversion problem: barriers and opportunities
Nearest neighbor representations of Boolean functions
Perspective on complexity measures targeting read-once branching programs
Notes on Boolean read-\(k\) and multilinear circuits
Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
Title not available (Why is that?)
Grafting key trees: efficient key management for overlapping groups
Symmetrizable Boolean networks
Randomized versus deterministic decision tree size
Title not available (Why is that?)
What circuit classes can be learned with non-trivial savings?
Title not available (Why is that?)
Approximate Degree in Classical and Quantum Computing
Bounds in ontology-based data access via circuit complexity
On expressing majority as a majority of majorities
Flipping out with many flips: hardness of testing \(k\)-monotonicity
Improvement of nonmonotone complexity estimates of \(k\)-valued logic functions
On the meaning of works by V. M. Khrapchenko
Bounded-depth Frege complexity of Tseitin formulas for all graphs
Quadratic lower bounds for algebraic branching programs and formulas
Tropical complexity, Sidon sets, and dynamic programming
Exact value of the nonmonotone complexity of Boolean functions
On the decision tree complexity of threshold functions
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?)

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)