No label defined (Q5140848)

From MaRDI portal

Jump to:navigation, search

scientific article; zbMATH DE number 7286923

Language	Label	Description	Also known as
English	No label defined	scientific article; zbMATH DE number 7286923

Statements

scholarly article

0 references

Theory of Computing

0 references

publication date

17 December 2020

0 references

zbMATH Keywords

circuit complexity

0 references

communication complexity

0 references

proof complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.4086/toc.2020.v016a013

0 references

The monotone circuit complexity of Boolean functions

0 references

The Potential of the Approximation Method

0 references

0 references

A combinatorial characterization of resolution width

0 references

Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity

0 references

Short proofs are narrow—resolution made simple

0 references

Symmetric approximation arguments for monotone lower bounds without sunflowers

0 references

Lower bounds for cutting planes proofs with small coefficients

0 references

Simulation theorems via pseudo-random properties

0 references

On the complexity of cutting-plane proofs

0 references

A characterization of span program size and improved lower bounds for monotone span programs

0 references

Monotone circuit lower bounds from resolution

0 references

Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)

0 references

Rectangles Are Nonnegative Juntas

0 references

Communication Lower Bounds via Critical Block Sensitivity

0 references

Deterministic Communication vs. Partition Number

0 references

Query-to-Communication Lifting for BPP

0 references

0 references

An exponential lower bound for the size of monotone real circuits

0 references

A note on monotone real circuits

0 references

On the virtue of succinct proofs

0 references

Boolean function complexity. Advances and frontiers.

0 references

Monotone Circuits for Connectivity Require Super-Logarithmic Depth

0 references

Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic

0 references

Discretely ordered modules as a first-order extension of the cutting planes proof system

0 references

Communication Complexity

0 references

Search Problems in the Decision Tree Model

0 references

A fast parallel algorithm to compute the rank of a matrix over an arbitrary field

0 references

Lower bounds for resolution and cutting plane proofs and monotone computations

0 references

Proofs as Games

0 references

Communication Complexity

0 references

Separation of the monotone NC hierarchy

0 references

Resolution over linear equations and multilinear proofs

0 references

0 references

Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

0 references

A New Kind of Tradeoffs in Propositional Proof Complexity

0 references

The Monotone Complexity of $k$-Clique on Random Graphs

0 references

On the bottleneck counting argument

0 references

Dag-like communication and its applications

0 references

The gap between monotone and non-monotone circuit complexity is exponential

0 references

Hard examples for resolution

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

10.4086/toc.2020.v016a013

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5140848

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q5140848&oldid=36640769"