scientific article; zbMATH DE number 1929951
From MaRDI portal
Publication:4708583
zbMath1023.94550MaRDI QIDQ4708583
Publication date: 18 June 2003
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2420/24200353.htm
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (30)
Lower bound of circuit complexity of parity function in a basis of unbounded fan-in ⋮ On the limits of gate elimination ⋮ The complexity of depth-3 circuits computing symmetric Boolean functions ⋮ Local reduction ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Lower Bounds for the Size of Nondeterministic Circuits ⋮ A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ Unnamed Item ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ On the power of nondeterministic circuits and co-nondeterministic circuits ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Reductions for monotone Boolean circuits ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Unnamed Item ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ New upper bounds on the Boolean circuit complexity of symmetric functions ⋮ Negation-limited formulas ⋮ Unnamed Item ⋮ Negation-limited complexity of parity and inverters ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ PAC-learning gains of Turing machines over circuits and neural networks ⋮ New lower bounds on circuit size of multi-output functions
This page was built for publication:
