scientific article; zbMATH DE number 1142303

Cited in

(77)

Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences
Negation-limited complexity of parity and inverters
Parameterized circuit complexity and the \(W\) hierarchy
ERCW PRAMs and optical communication
Matching theory -- a sampler: From Dénes König to the present
Separating complexity classes related to -decision trees
The computational complexity of universal hashing
Relating polynomial time to constant depth
Reductions in circuit complexity: An isomorphism theorem and a gap theorem
Positive versions of polynomial time
An exponential lower bound for the size of monotone real circuits
Characterizing linear size circuits in terms of privacy
The relative power of logspace and polynomial time reductions
Shallow circuits and concise formulae for multiple addition and multiplication
Directed monotone contact networks for threshold functions
Complexity models for incremental computation
\(\Sigma\Pi\Sigma\) threshold formulas
On ACC
On almost bad Boolean bases
Query languages for bags and aggregate functions
A query language for NC
On the complexity of entailment in propositional multivalued logics
Gap-languages and log-time complexity classes
Optimal bounds for the approximation of Boolean functions and some applications
Some connections between bounded query classes and non-uniform complexity.
Time-space tradeoffs for satisfiability
The complexity of belief update
No feasible monotone interpolation for simple combinatorial reasoning
Can large fanin circuits perform reliable computations in the presence of faults?
Which problems have strongly exponential complexity?
The expressiveness of DAC
Circuit and decision tree complexity of some number theoretic problems
Preprocessing of intractable problems
On the negation-limited circuit complexity of merging
On learning monotone DNF under product distributions
Evaluating spectral norms for constant depth circuits with symmetric gates
Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
Circuit complexity of linear functions: gate elimination and feeble security
The size of a revised knowledge base
Feasibly constructive proofs of succinct weak circuit lower bounds
Mining circuit lower bound proofs for meta-algorithms
Partition-based logical reasoning for first-order and propositional theories
Using the renormalization group to classify Boolean functions
Boolean expression diagrams
Monotone real circuits are more powerful than monotone Boolean circuits
The average sensitivity of bounded-depth circuits
Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
A feasible interpolation for random resolution
Depth of Boolean functions realized by circuits over an arbitrary infinite basis
On derandomization and average-case complexity of monotone functions
Small bias requires large formulas
Hardness magnification near state-of-the-art lower bounds
Parameterized Parallel Computing and First-Order Logic
Hardness magnification near state-of-the-art lower bounds
The complexity of graph connectivity
Partial-order Boolean games: informational independence in a logic-based model of strategic interaction
The communication complexity of addition
Pac-learning non-recursive Prolog clauses
Pac-learning non-recursive Prolog clauses
On BPP versus \(NP\cup coNP\) for ordered read-once branching programs
On log-time alternating Turing machines of alternation depth k
The strongest model of computation obeying 0-1 Principles
Circuit complexity before the dawn of the new millennium
Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
Negation-limited circuit complexity of symmetric functions
Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
On input read-modes of alternating Turing machines
Interpolants, cut elimination and flow graphs for the propositional calculus
On the computation of Boolean functions by analog circuits of bounded fan-in
Improvements on Khrapchenko's theorem
Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
Answering fuzzy queries over fuzzy DL-Lite ontologies
Clique is not solvable by monotone circuits of polynomial size
An extension of Khrapchenko's theorem
On the complexity of second-best abductive explanations
On the complexity of cutting-plane proofs using split cuts
Smallest formulas for the parity of \(2^k\) variables are essentially unique

This page was built for publication:

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