A complexity theory based on Boolean algebra
From MaRDI portal
Recommendations
Cited in
(38)- Threshold functions and bounded depth monotone circuits
- The monotone circuit complexity of Boolean functions
- Feasible arithmetic computations: Valiant's hypothesis
- There are no p-complete families of symmetric Boolean functions
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On monotone simulations on nonmonotone networks
- Properties that characterize LOGCFL
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- Nonuniform complexity and the randomness of certain complete languages
- The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
- Using the Hamiltonian path operator to capture NP
- Completeness and non-completeness results with respect to read-once projections
- Complexity models for incremental computation
- A reducibility concept for problems defined in terms of ordered binary decision diagrams
- Gap-languages and log-time complexity classes
- On the algebraic complexity of some families of coloured Tutte polynomials
- Expressiveness of matchgates.
- Threshold circuits of bounded depth
- Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
- An exponential lower bound for homogeneous depth four arithmetic formulas
- A theory of boolean integration
- scientific article; zbMATH DE number 3896920 (Why is no real title available?)
- scientific article; zbMATH DE number 3936520 (Why is no real title available?)
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- Some results on uniform arithmetic circuit complexity
- scientific article; zbMATH DE number 1498465 (Why is no real title available?)
- Lower bounds for the majority communication complexity of various graph accessibility problems
- Uniform Constraint Satisfaction Problems and Database Theory
- On pseudorandomness and resource-bounded measure
- Dot operators
- Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
- Complete problems for monotone NP
- Methods for proving completeness via logical reductions
- Hypertree decompositions and tractable queries
- A measure in which Boolean negation is exponentially powerful
- Weighted hypertree decompositions and optimal query plans
- Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
- Polynomial size \(\Omega\)-branching programs and their computational power
This page was built for publication: A complexity theory based on Boolean algebra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3771612)
