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