Boolean function complexity. Advances and frontiers.

DOI10.1007/978-3-642-24508-4MaRDI QIDQ642463zbMATH OpenOpenAlexFDO

Authors Stasys 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

Cited in

(only showing first 100 items - show all)

A short proof that the extension complexity of the correlation polytope grows exponentially
Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
Grafting key trees: efficient key management for overlapping groups
Extension complexity of independent set polytopes
scientific article; zbMATH DE number 7561750 (Why is no real title available?)
scientific article; zbMATH DE number 1775052 (Why is no real title available?)
What circuit classes can be learned with non-trivial savings?
Symmetrizable Boolean networks
Randomized versus deterministic decision tree size
On the binary and Boolean rank of regular matrices
scientific article; zbMATH DE number 7561559 (Why is no real title available?)
Approximate Degree in Classical and Quantum Computing
Bounds in ontology-based data access via circuit complexity
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
Hardness magnification near state-of-the-art lower bounds
On expressing majority as a majority of majorities
Flipping out with many flips: hardness of testing \(k\)-monotonicity
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
Adventures in monotone complexity and TFNP
Recent progress in the Boolean domain
On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
Lower Bounds for DeMorgan Circuits of Bounded Negation Width
scientific article; zbMATH DE number 7250145 (Why is no real title available?)
Improvement of nonmonotone complexity estimates of \(k\)-valued logic functions
A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
On the meaning of works by V. M. Khrapchenko
Bounded-depth Frege complexity of Tseitin formulas for all graphs
Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
Limitations of incremental dynamic programming
On the extension complexity of polytopes separating subsets of the Boolean cube
Quadratic lower bounds for algebraic branching programs and formulas
New bounds for energy complexity of Boolean functions
Local bounds for the optimal information ratio of secret sharing schemes
Tropical complexity, Sidon sets, and dynamic programming
Exact value of the nonmonotone complexity of Boolean functions
Lifting Theorems for Equality
On the decision tree complexity of threshold functions
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
scientific article; zbMATH DE number 194333 (Why is no real title available?)
Mining circuit lower bound proofs for meta-algorithms
Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
The computational complexity of equivalence and isomorphism problems
scientific article; zbMATH DE number 5852793 (Why is no real title available?)
scientific article; zbMATH DE number 4012495 (Why is no real title available?)
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
On compiling structured CNFs to OBDDs
Complexity of quantum circuits via sensitivity, magic, and coherence
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
Lower bounds for tropical circuits and dynamic programs
PAC-learning gains of Turing machines over circuits and neural networks
Power of uninitialized qubits in shallow quantum circuits
Circuit complexity before the dawn of the new millennium
A note on the size of prenex normal forms
Separating OR, SUM, and XOR circuits
On the resolution of the sensitivity conjecture
On various nonlinearity measures for Boolean functions
The price of query rewriting in ontology-based data access
Tropical Circuit Complexity
Worst-Case to Average-Case Reductions for Subclasses of P
On the hardness of approximate and exact (bichromatic) maximum inner product
Circuit complexity meets ontology-based data access
On separation between the degree of a Boolean function and the block sensitivity
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
Expander-based cryptography meets natural proofs
Algorithms and lower bounds for comparator circuits from shrinkage
Testing \(k\)-monotonicity
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Rectangles are nonnegative juntas
On the mystery of negations in circuits: structure vs power
Monotone classes beyond VNP
Regular expression length via arithmetic formula complexity
scientific article; zbMATH DE number 7250155 (Why is no real title available?)
On the limits of gate elimination
MaxSAT Resolution and Subcube Sums
String Matching: Communication, Circuits, and Learning.
On (simple) decision tree rank
Alternation, sparsity and sensitivity: bounds and exponential gaps
Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
On the read-once property of branching programs and CNFs of bounded treewidth
Negation-limited formulas
Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic
Stabbing planes
ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
Cutting planes cannot approximate some integer programs
On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
scientific article; zbMATH DE number 7471677 (Why is no real title available?)
Book review of: S. Jukna, Boolean function complexity. Advances and frontiers.
A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
Monotone circuit lower bounds from resolution
Formula complexity of a linear function in a \(k\)-ary basis
The landscape of communication complexity classes
Clique problem, cutting plane proofs and communication complexity
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
Constructive relationships between algebraic thickness and normality
One-tape Turing machine and branching program lower bounds for MCSP
Depth-3 circuits for inner product

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)