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)

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
Deterministic communication vs. partition number
On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
Query-to-communication lifting for BPP
Nondeterministic and randomized Boolean hierarchies in communication complexity
Counting the number of perfect matchings, and generalized decision trees
Flipping out with many flips: hardness of testing \(k\)-monotonicity
scientific article; zbMATH DE number 176868 (Why is no real title available?)
Improved bounds on the an-complexity of \(O(1)\)-linear functions
On compiling structured CNFs to OBDDs
Cancellation-free circuits in unbounded and bounded depth
Hardness magnification near state-of-the-art lower bounds
Upper bounds for the formula size of symmetric Boolean functions
CNF encodings of symmetric functions
On the CNF-complexity of bipartite graphs containing no squares
Non-commutative circuits and the sum-of-squares problem
On the complexity of multivalued logic functions over some infinite basis
Partial order games
Lower bounds for Boolean circuits of bounded negation width
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
Upper bounds for the size and the depth of formulae for MOD-functions
Formulas versus Circuits for Small Distance Connectivity
Zero-information protocols and unambiguity in Arthur-Merlin communication
scientific article; zbMATH DE number 7228448 (Why is no real title available?)
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
Random arithmetic formulas can be reconstructed efficiently
Circuit lower bounds from learning-theoretic approaches
Skew circuits of small width
The function-inversion problem: barriers and opportunities
On the Decision Tree Complexity of Threshold Functions
scientific article; zbMATH DE number 7250154 (Why is no real title available?)
Nearest neighbor representations of Boolean functions
Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
The minimum number of negations in circuits for systems of multi-valued functions
No small nondeterministic read-once branching programs for CNFs of bounded treewidth
Perspective on complexity measures targeting read-once branching programs
Notes on Boolean read-\(k\) and multilinear circuits
Multiplicative complexity of vector valued Boolean functions

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)