scientific article; zbMATH DE number 4008289
From MaRDI portal
Publication:3758729
Recommendations
Cited in
(only showing first 100 items - show all)- Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
- On almost bad Boolean bases
- Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences
- Monotone circuit lower bounds from robust sunflowers
- Monotone simulations of non-monotone proofs.
- scientific article; zbMATH DE number 176869 (Why is no real title available?)
- Randomized feasible interpolation and monotone circuits with a local oracle
- Lower bounds for monotone \(q\)-multilinear Boolean circuits
- Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
- scientific article; zbMATH DE number 4217938 (Why is no real title available?)
- Satisfiability, branch-width and Tseitin tautologies
- Lower bounds for Boolean circuits of bounded negation width
- Resolution over linear equations and multilinear proofs
- The complexity of central slice functions
- Characterizing propositional proofs as noncommutative formulas
- A method for obtaining efficient lower bounds for monotone complexity
- On lengths of proofs in non-classical logics
- On monotone simulations on nonmonotone networks
- Switching functions whose monotone complexity
- Towards NP-P via proof complexity and search
- The gap between monotone and non-monotone circuit complexity is exponential
- scientific article; zbMATH DE number 4095386 (Why is no real title available?)
- An exponential lower bound for the size of monotone real circuits
- Matchings and covers in hypergraphs
- A note on the power of majority gates and modular gates
- Monotone circuit lower bounds from resolution
- On sunflowers and matrix multiplication
- On reducibility and symmetry of disjoint NP pairs.
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- A lower bound for the shortest path problem
- On the complexity of cutting-plane proofs using split cuts
- scientific article; zbMATH DE number 3916178 (Why is no real title available?)
- Threshold circuits of bounded depth
- Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables
- Negation-limited circuit complexity of symmetric functions
- Tradeoffs for language recognition on alternating machines
- A lower bound for the affinity level for almost all Boolean functions
- Circuit complexity meets ontology-based data access
- Lower bounds for monotone span programs
- Negation-limited formulas
- Lower bounds for tropical circuits and dynamic programs
- One-way permutations, computational asymmetry and distortion.
- Lower bounds for monotone counting circuits
- On algorithm complexity
- An exponential gap with the removal of one negation gate
- Exact solution of some Turán-type problems
- A lower bound for intuitionistic logic
- Matching theory -- a sampler: From Dénes König to the present
- Natural proofs
- Some structural properties of low-rank matrices related to computational complexity
- Very large cliques are easy to detect
- Large clique is hard on average for resolution
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Nonuniform ACC circuit lower bounds
- scientific article; zbMATH DE number 609922 (Why is no real title available?)
- Cutting planes cannot approximate some integer programs
- Reductions for monotone Boolean circuits
- Monotone real circuits are more powerful than monotone Boolean circuits
- A sorting network in bounded arithmetic
- A lower bound for read-once-only branching programs
- Clique problem, cutting plane proofs and communication complexity
- Limiting negations in non-deterministic circuits
- Nondeterministic functions and the existence of optimal proof systems
- Localizability of the approximation method
- Logic circuits from zero forcing
- Circuit lower bounds for average-case MA
- Proof complexity of monotone branching programs
- Pseudo sunflowers
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Sunflowers and quasi-sunflowers from randomness extractors
- A recursion-theoretic characterisation of the positive polynomial-time functions
- Affine projections of symmetric polynomials.
- scientific article; zbMATH DE number 1418485 (Why is no real title available?)
- Unprovability of strong complexity lower bounds in bounded arithmetic
- scientific article; zbMATH DE number 7564405 (Why is no real title available?)
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Notes on Boolean read-\(k\) and multilinear circuits
- On Negations in Boolean Networks
- Circuit lower bounds from learning-theoretic approaches
- Monotone complexity of a pair
- \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
- Secret-sharing for NP
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- On the bottleneck counting argument
- What circuit classes can be learned with non-trivial savings?
- On the mean complexity of monotone functions
- Bounds for the average-case complexity of monotone Boolean functions
- scientific article; zbMATH DE number 1746571 (Why is no real title available?)
- Evaluating spectral norms for constant depth circuits with symmetric gates
- On the mystery of negations in circuits: structure vs power
- scientific article; zbMATH DE number 3943711 (Why is no real title available?)
- The price of query rewriting in ontology-based data access
- scientific article; zbMATH DE number 4008290 (Why is no real title available?)
- scientific article; zbMATH DE number 3867233 (Why is no real title available?)
- The canonical pairs of bounded depth Frege systems
- Bounds in ontology-based data access via circuit complexity
- Frege proof system and TNC°
- Lower Bounds for DeMorgan Circuits of Bounded Negation Width
- Sunflowers: from soil to oil
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 Q3758729)
