Pages that link to "Item:Q1095871"

The following pages link to Lower bounds on the size of bounded depth circuits over a complete basis with logical addition (Q1095871):

Displaying 50 items.

• Correlation lower bounds from correlation upper bounds (Q280948) (← links)
• A lower bound for depth-3 circuits with MOD \(m\) gates (Q293324) (← links)
• Finding all solutions of equations in free groups and monoids with involution (Q342722) (← links)
• Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields (Q395606) (← links)
• Towards NP-P via proof complexity and search (Q408544) (← links)
• Exponential lower bound for bounded depth circuits with few threshold gates (Q413295) (← links)
• Random low-degree polynomials are hard to approximate (Q430841) (← links)
• Isomorphism testing of Boolean functions computable by constant-depth circuits (Q476155) (← links)
• Lower bounds against weakly-uniform threshold circuits (Q486977) (← links)
• On \(d\)-multiplicative secret sharing (Q604627) (← links)
• On systems of equations over free products of groups. (Q651246) (← links)
• A note on the power of majority gates and modular gates (Q673905) (← links)
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy (Q685431) (← links)
• On the power of small-depth threshold circuits (Q685717) (← links)
• Makanin-Razborov diagrams over free products. (Q716389) (← links)
• Non-uniform automata over groups (Q804303) (← links)
• Lower bounds for constant-depth circuits in the presence of help bits (Q917289) (← links)
• Lower bounds for recognizing small cliques on CRCW PRAM's (Q919820) (← links)
• Generalizing proofs in monadic languages (with a postscript by Georg Kreisel). (Q930260) (← links)
• The complexity of symmetric functions in bounded-depth circuits (Q1107989) (← links)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) (Q1117696) (← links)
• On the relative complexity of some languages in \(NC^ 1\) (Q1124355) (← links)
• Some notes on threshold circuits, and multiplication in depth 4 (Q1182104) (← links)
• An arithmetic model of computation equivalent to threshold circuits (Q1186610) (← links)
• A simple lower bound for monotone clique using a communication game (Q1190521) (← links)
• Regular languages in \(NC\) (Q1191027) (← links)
• The complexity of computing symmetric functions using threshold circuits (Q1193637) (← links)
• Separating complexity classes related to \(\Omega\)-decision trees (Q1202936) (← links)
• On read-once threshold formulae and their randomized decision tree complexity (Q1208407) (← links)
• The computational efficacy of finite-field arithmetic (Q1210295) (← links)
• Solutions of quadratic equations in groups with small cancellation condition (Q1262952) (← links)
• On the computational power of depth-2 circuits with threshold and modulo gates (Q1269909) (← links)
• Threshold circuits of small majority-depth (Q1273878) (← links)
• Algebraic geometry over groups. I: Algebraic sets and ideal theory (Q1306828) (← links)
• Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC (Q1317485) (← links)
• Exact lower time bounds for computing Boolean functions on CREW PRAMs (Q1329159) (← links)
• The expressive power of voting polynomials (Q1330793) (← links)
• On the degree of Boolean functions as real polynomials (Q1346612) (← links)
• On ACC (Q1346616) (← links)
• Representing Boolean functions as polynomials modulo composite numbers (Q1346617) (← links)
• Circuits constructed with MOD\(_ q\) gates cannot compute ``and'' in sublinear size (Q1346618) (← links)
• A note on a theorem of Barrington, Straubing and Thérien (Q1351160) (← links)
• Predicting nonlinear cellular automata quickly by decomposing them into linear ones (Q1376426) (← links)
• Algebraic methods and bounded formulas (Q1377552) (← links)
• Reflections on ``Representations of sets of Boolean functions by commutative rings'' by Roman Smolensky (Q1377573) (← links)
• Upper and lower bounds for some depth-3 circuit classes (Q1377575) (← links)
• Irreducible affine varieties over a free group. I: Irreducibility of quadratic equations and Nullstellensatz (Q1383968) (← links)
• Irreducible affine varieties over a free group. II: Systems in triangular quasi-quadratic form and description of residually free groups (Q1383969) (← links)
• On the power of circuits with gates of low \(L_{1}\) norms. (Q1389652) (← links)
• Finite semigroup varieties defined by programs (Q1390876) (← links)