scientific article

zbMath0621.94027MaRDI QIDQ3758729

Alexander A. Razborov

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

monotone Boolean functionmonotone complexityconstructive sequences

Mathematics Subject Classification ID

Related Items (86)

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

This page was built for publication: