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