{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T03:06:20Z","timestamp":1777777580436,"version":"3.51.4"},"reference-count":110,"publisher":"Emerald","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,10,31]]},"abstract":"<jats:p>How to compute a linear Boolean operator by a small circuit using only unbounded fanin addition gates? Because this question is about one of the simplest and most basic circuit models, it has been considered by many authors since the early 1950s. This has led to a variety of upper and lower bound arguments\u2014ranging from algebraic (determinant and matrix rigidity), to combinatorial (Ramsey properties, coverings, and decompositions) to graph-theoretic (the superconcentrator method). We provide a thorough survey of the research in this direction, and prove some new results to fill out the picture. The focus is on the cases in which the addition operation is either the boolean OR or XOR, but the model in which arbitrary boolean functions are allowed as gates is considered as well.<\/jats:p>","DOI":"10.1561\/0400000063","type":"journal-article","created":{"date-parts":[[2013,10,30]],"date-time":"2013-10-30T11:57:07Z","timestamp":1383134227000},"page":"1-123","source":"Crossref","is-referenced-by-count":19,"title":["Complexity of Linear Boolean Operators"],"prefix":"10.1108","volume":"9","author":[{"given":"Stasys","family":"Jukna","sequence":"first","affiliation":[{"name":"Vilnius University, Lithuania and Frankfurt University ,","place":["Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Sergeev","sequence":"additional","affiliation":[{"name":"Lomonosov Moscow State University ,","place":["Russia"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","published-online":{"date-parts":[[2013,10,31]]},"reference":[{"key":"2026040314242756600_ref001","first-page":"259","article-title":"Two constructions of difference sets","volume":"38","author":"Alexeev","year":"1981","journal-title":"Problemy Kibernetiki"},{"issue":"3","key":"2026040314242756600_ref002","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF02579382","article-title":"Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory","volume":"6","author":"Alon","year":"1986","journal-title":"Combinatorica"},{"issue":"6","key":"2026040314242756600_ref003","doi-asserted-by":"crossref","first-page":"1064","DOI":"10.1137\/0219074","article-title":"Linear circuits over GF(2)","volume":"19","author":"Alon","year":"1990","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2026040314242756600_ref004","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0022-0000(88)90002-5","article-title":"Meanders and their applications in lower bounds arguments","volume":"37","author":"Alon","year":"1988","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"2026040314242756600_ref005","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/S0022-0000(05)80027-3","article-title":"Superconcentrators of depths 2 and 3; odd levels help (rarely)","volume":"48","author":"Alon","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"key":"2026040314242756600_ref006","first-page":"11","volume-title":"Physical and mathematical modeling of discrete systems","author":"Andreev","year":"1985"},{"issue":"2","key":"2026040314242756600_ref007","first-page":"97","article-title":"On a family of Boolean matrices","volume":"41","author":"Andreev","year":"1986","journal-title":"Vestnik Moskow Univ."},{"key":"2026040314242756600_ref008","volume-title":"Extremal graph theory","author":"Bollob\u00e1s","year":"1978"},{"key":"2026040314242756600_ref009","first-page":"1","article-title":"An affine analogue of Singer\u2019s theorem","volume":"6","author":"Bose","year":"1942","journal-title":"J. Indian Math. Soc."},{"key":"2026040314242756600_ref010","article-title":"Cancellation-free circuits: An approach for proving superlinear lower bounds for linear boolean operators","volume-title":"Technical report","author":"Boyar","year":"2012"},{"key":"2026040314242756600_ref011","article-title":"Cancellation-free circuits in unbounded and bounded depth","volume-title":"Technical report","author":"Boyar","year":"2013"},{"issue":"6","key":"2026040314242756600_ref012","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1007\/BF00264314","article-title":"Decomposition of graphs and monotone formula size of homogeneous functions","volume":"23","author":"Bublitz","year":"1986","journal-title":"Acta Inf."},{"key":"2026040314242756600_ref013","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic complexity theory","author":"B\u00fcrgisser","year":"1997"},{"issue":"2","key":"2026040314242756600_ref014","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/0022-0000(85)90015-7","article-title":"Unbounded fan-in circuits and associative functions","volume":"30","author":"Chandra","year":"1985","journal-title":"J. Comput. Syst. Sci."},{"key":"2026040314242756600_ref015","first-page":"109","article-title":"Lower bounds for constant depth circuits for prefix problems","volume-title":"Proc. in 10th Int. Colloq. on Automata, Languages and Programming (ICALP)","author":"Chandra","year":"1983"},{"key":"2026040314242756600_ref016","first-page":"56","volume-title":"Transactions on Discrete Mathematics and its Applications","author":"Chashkin","year":"2009"},{"key":"2026040314242756600_ref017","article-title":"On linear operators injective on subsets of the space GFn(p)","author":"Chashkin","year":"2013","journal-title":"Discrete Mathematics and Applications"},{"issue":"1","key":"2026040314242756600_ref018","first-page":"109","article-title":"On complexity of linear operators on the class of circuits of depth 2","volume":"20","author":"Cherukhin","year":"2008","journal-title":"Diskretnaya Matematika"},{"issue":"4","key":"2026040314242756600_ref019","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1515\/dma.2011.031","article-title":"Lower bounds for complexity of boolean circuits of finite depth with arbitrary elements","volume":"21","author":"Cherukhin","year":"2011","journal-title":"Discrete Mathematics and Applications"},{"issue":"2","key":"2026040314242756600_ref020","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0217015","article-title":"Unbiased bits from sources of weak randomness and probabilistic communication complexity","volume":"17","author":"Chor","year":"1988","journal-title":"SIAM J. Comput."},{"key":"2026040314242756600_ref021","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-3-0348-5438-2_10","volume-title":"Studies in Pure Mathematics, To the Memory of Paul Tur\u00e1n","author":"Chung","year":"1983"},{"key":"2026040314242756600_ref022","first-page":"42","article-title":"Superconcentrators, generalizers and generalized connectors with limited depth (preliminary version)","volume-title":"Proc. of 15th Ann. ACM Symp. on Theory of Computing","author":"Dolev","year":"1983"},{"key":"2026040314242756600_ref023","first-page":"170","article-title":"Limitations of lower-bound methods for the wire complexity of boolean operators","volume-title":"IEEE Conference on Computational Complexity","author":"Drucker","year":"2012"},{"key":"2026040314242756600_ref024","volume-title":"The complexity of Boolean networks","author":"Dunne","year":"1988"},{"key":"2026040314242756600_ref025","first-page":"257","article-title":"More on a problem of Zarankiewicz","volume-title":"Proc. of 23rd Int. Symp. on Algorithms and Computation, ISAAC 2012","author":"Dutta","year":"2012"},{"key":"2026040314242756600_ref026","first-page":"365","volume-title":"Computers and Math. with Appl.","author":"Erd\u0151s","year":"1976"},{"key":"2026040314242756600_ref027","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1112\/jlms\/s1-35.1.85","article-title":"Intersection theorems for systems of sets","volume":"35","author":"Erd\u0151s","year":"1960","journal-title":"J. London Math. Soc"},{"key":"2026040314242756600_ref028","volume-title":"Probabilistic methods in combinatorics","author":"Erd\u0151s","year":"1974"},{"issue":"2","key":"2026040314242756600_ref029","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1006\/jcss.1995.1065","article-title":"Clique partitions, graph compression and speeding-up algorithms","volume":"51","author":"Feder","year":"1995","journal-title":"J. Comput. Syst. Sci."},{"key":"2026040314242756600_ref030","article-title":"Separating OR, SUM, and XOR circuits","volume-title":"Technical report","author":"Find","year":"2013"},{"issue":"2","key":"2026040314242756600_ref031","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF01303207","article-title":"A note on matrix rigidity","volume":"13","author":"Friedman","year":"1993","journal-title":"Combinatorica"},{"key":"2026040314242756600_ref032","first-page":"234","article-title":"On the complexity of realization of some classes of matrices by rectifier networks","volume":"1","author":"G\u00e1l","year":"1988","journal-title":"Matematicheskije Voprosy Kibernetiki"},{"key":"2026040314242756600_ref033","first-page":"479","article-title":"Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates","volume-title":"STOC 2012","author":"G\u00e1l","year":"2012"},{"issue":"3","key":"2026040314242756600_ref034","first-page":"3","article-title":"On the complexity of linear boolean operators with thin matrices","volume":"17","author":"Gashkov","year":"2010","journal-title":"Diskretn. Anal. Issled. Oper."},{"issue":"10","key":"2026040314242756600_ref035","first-page":"33","article-title":"A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials","volume":"203","author":"Gashkov","year":"2012","journal-title":"Matematicheskii Sbornik"},{"key":"2026040314242756600_ref036","first-page":"26","volume-title":"Studies in Complexity and Cryptography","author":"Goldreich","year":"2011"},{"key":"2026040314242756600_ref037","first-page":"38","volume-title":"Notes of the Scientific Seminar Leningrad branch of the Steklov Institute","author":"Grigoriev","year":"1976"},{"key":"2026040314242756600_ref038","first-page":"19","volume-title":"Notes of the Scientific Seminar Leningrad branch of the Steklov Institute","author":"Grigoriev","year":"1977"},{"key":"2026040314242756600_ref039","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0304-3975(82)90014-7","article-title":"Additive complexity in directed computations","volume":"19","author":"Grigoriev","year":"1982","journal-title":"Theoret. Comput Sci."},{"key":"2026040314242756600_ref040","first-page":"25","volume-title":"Notes of the Scientific Seminar Leningrad branch of the Steklov Institute","author":"Grigoriev","year":"1982"},{"key":"2026040314242756600_ref041","first-page":"3","article-title":"On the complexity of realization of boolean triangular matrices by rectifier schemes of various depths","volume":"4","author":"Grinchuk","year":"1986","journal-title":"Metody Diskretnogo Analiza"},{"key":"2026040314242756600_ref042","first-page":"39","article-title":"Complexity of the realization of cyclic boolean matrices by gate circuits","volume":"7","author":"Grinchuk","year":"1988","journal-title":"Izvestija VUZov. Matematika"},{"issue":"5","key":"2026040314242756600_ref043","first-page":"38","article-title":"Thin circulant matrices and lower bounds on the complexity of some boolean operators","volume":"18","author":"Grinchuk","year":"2011","journal-title":"Diskretn. Anal. Issled. Oper."},{"issue":"25","key":"2026040314242756600_ref044","first-page":"6037","article-title":"Nombre minimal de contacts de fermeture n\u00e9cessaires pour r\u00e9aliser une fonction bool\u00e9enne sym\u00e9trique de n variables","volume":"258","author":"Hansel","year":"1964","journal-title":"C. R. Acad. Sci."},{"key":"2026040314242756600_ref045","volume-title":"Inequalities","author":"Hardy","year":"1934"},{"key":"2026040314242756600_ref046","first-page":"319","article-title":"Towards a better understanding of one-wayness: facing linear permutations","volume-title":"EUROCRYPT","author":"Hiltgen","year":"1998"},{"issue":"1","key":"2026040314242756600_ref047","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/S0097539705447001","article-title":"Disproving the single level conjecture","volume":"36","author":"Jukna","year":"2006","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2026040314242756600_ref048","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s00224-008-9133-y","article-title":"Entropy of operators or why matrix multiplication is hard for depth-two circuits","volume":"46","author":"Jukna","year":"2010","journal-title":"Theory of Computing Systems"},{"key":"2026040314242756600_ref049","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/j.disc.2009.07.011","article-title":"Representing (0,1)-matrices by depth-2 circuits with arbitrary gates","volume":"310","author":"Jukna","year":"2010","journal-title":"Discrete Mathematics"},{"key":"2026040314242756600_ref050","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-24508-4","volume-title":"Boolean Function Complexity","author":"Jukna","year":"2012"},{"issue":"6","key":"2026040314242756600_ref051","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1016\/j.jcss.2009.09.003","article-title":"Min-rank conjecture for log-depth circuits","volume":"77","author":"Jukna","year":"2011","journal-title":"J. Comput. Syst. Sci."},{"key":"2026040314242756600_ref052","first-page":"23","article-title":"On a problem of graph theory","volume":"2","author":"Katona","year":"1967","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"issue":"4","key":"2026040314242756600_ref053","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s10986-012-9181-5","article-title":"On the CNF-complexity of bipartite graphs containing no squares","volume":"52","author":"Katz","year":"2012","journal-title":"Lithuanian Math. Journal"},{"issue":"2","key":"2026040314242756600_ref054","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1016\/0304-3975(94)90135-X","article-title":"Shallow grates","volume":"123","author":"Klawe","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"2026040314242756600_ref055","volume-title":"Art of programming: seminumerical algorithms","author":"Knuth","year":"1997","edition":"Third Edition"},{"key":"2026040314242756600_ref056","first-page":"51","article-title":"On the complexity of rectifier networks with multiple number of paths","volume-title":"Materials of the 18-th International School on Synthesis and Complexity of Control Systems","author":"Kochergin","year":"2009"},{"issue":"3","key":"2026040314242756600_ref057","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1007\/BF01261323","article-title":"Norm-graphs and bipartite Tur\u00e1n numbers","volume":"16","author":"Koll\u00e1r","year":"1996","journal-title":"Combinatorica"},{"key":"2026040314242756600_ref058","doi-asserted-by":"crossref","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","article-title":"On a problem of K. Zarankiewicz","volume":"3","author":"K\u00f6vari","year":"1954","journal-title":"Colloq. Math."},{"issue":"4","key":"2026040314242756600_ref059","first-page":"803","article-title":"Complexity of contact circuits realizing a function of logical algebra","volume":"151","author":"Krichevski","year":"1963","journal-title":"Doklady Akad. Nauk SSSR"},{"key":"2026040314242756600_ref060","volume-title":"Introduction to Finite Fields and their Applications","author":"Lidl","year":"1986"},{"issue":"1-2","key":"2026040314242756600_ref061","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000011","article-title":"Complexity lower bounds using linear algebra","volume":"4","author":"Lokam","year":"2009","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"2026040314242756600_ref062","first-page":"1171","article-title":"On rectifier and switching-and-rectifier schemes","volume":"111","author":"Lupanov","year":"1956","journal-title":"Doklady Akad. Nauk SSSR"},{"issue":"4","key":"2026040314242756600_ref063","first-page":"311","article-title":"On rectifier schemes","volume":"4","author":"Lupanov","year":"1980","journal-title":"Acta Cybernetica"},{"key":"2026040314242756600_ref064","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/BF00268321","article-title":"Some remarks on Boolean sums","volume":"12","author":"Mehlhorn","year":"1979","journal-title":"Acta Informatica"},{"key":"2026040314242756600_ref065","first-page":"556","article-title":"Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries","volume-title":"SODA","author":"Miltersen","year":"1998"},{"issue":"4","key":"2026040314242756600_ref066","first-page":"773","article-title":"On linear Boolean operators","volume":"165","author":"Mitiagin","year":"1965","journal-title":"Doklady Akad. Nauk SSSR"},{"issue":"2","key":"2026040314242756600_ref067","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1145\/321752.321761","article-title":"Note on a lower bound of the linear complexity of the Fast Fourier Transform","volume":"20","author":"Morgenstern","year":"1973","journal-title":"J. of the ACM"},{"issue":"2","key":"2026040314242756600_ref068","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1145\/321879.321881","article-title":"The linear complexity of computation","volume":"22","author":"Morgenstern","year":"1974","journal-title":"J. of the ACM"},{"key":"2026040314242756600_ref069","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"key":"2026040314242756600_ref070","first-page":"49","article-title":"On multipolar switching circuits realizing functions of multi-valued logics","volume":"5","author":"Nechiporuk","year":"1961","journal-title":"Problemy Kybernetiki"},{"issue":"1","key":"2026040314242756600_ref071","first-page":"50","article-title":"Rectifier networks","volume":"148","author":"Nechiporuk","year":"1963","journal-title":"Doklady Akad. Nauk SSSR"},{"key":"2026040314242756600_ref072","first-page":"37","article-title":"On the synthesis of rectifier networks","volume":"9","author":"Nechiporuk","year":"1963","journal-title":"Problemy Kibernetiki"},{"issue":"5","key":"2026040314242756600_ref073","first-page":"1045","article-title":"Self-correcting diode networks","volume":"156","author":"Nechiporuk","year":"1964","journal-title":"Doklady Akad. Nauk SSSR"},{"key":"2026040314242756600_ref074","first-page":"237","article-title":"On a boolean matrix","volume":"21","author":"Nechiporuk","year":"1969","journal-title":"Problemy Kibernetiki"},{"key":"2026040314242756600_ref075","first-page":"5","article-title":"On the topological principles of self-correction","volume":"21","author":"Nechiporuk","year":"1969","journal-title":"Problemy Kibernetiki"},{"issue":"4","key":"2026040314242756600_ref076","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1137\/S0895480190283595","article-title":"Lower bounds on formula size of boolean functions using hypergraph entropy","volume":"8","author":"Newman","year":"1995","journal-title":"SIAM J. Discrete Math."},{"key":"2026040314242756600_ref077","first-page":"1","article-title":"A complete annotated bibliography of work related to Sidon sequences","volume":"11","author":"O\u2019Bryant","year":"2004","journal-title":"Electronic Journal of Combinatorics"},{"key":"2026040314242756600_ref078","first-page":"45","article-title":"Realization of \u201cnarrow\u201d matrices by rectifier networks","volume":"22","author":"Orlov","year":"1970","journal-title":"Problemy Kybernetiki"},{"key":"2026040314242756600_ref079","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0022-247X(68)90163-7","article-title":"Applications of Menger\u2019s graph theorem","volume":"22","author":"Perfect","year":"1968","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"2026040314242756600_ref080","article-title":"Biclique covers and partitions","volume-title":"Technical report","author":"Pinto","year":"2013"},{"key":"2026040314242756600_ref081","first-page":"258","article-title":"On the evaluation of powers and related problems","volume-title":"FOCS","author":"Pippenger","year":"1976"},{"issue":"2","key":"2026040314242756600_ref082","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0206022","article-title":"Superconcentrators","volume":"6","author":"Pippenger","year":"1977","journal-title":"SIAM J. Comput."},{"issue":"1","key":"2026040314242756600_ref083","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF01776581","article-title":"The minimum number of edges in graphs with prescribed paths","volume":"12","author":"Pippenger","year":"1979","journal-title":"Math. Syst. Theory"},{"key":"2026040314242756600_ref084","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(80)90034-1","article-title":"On another Boolean matrix","volume":"11","author":"Pippenger","year":"1980","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"2026040314242756600_ref085","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0022-0000(82)90056-3","article-title":"Superconcentrators of depth 2","volume":"24","author":"Pippenger","year":"1982","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"2026040314242756600_ref086","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01215351","article-title":"Communication in bounded depth circuits","volume":"14","author":"Pudl\u00e1k","year":"1994","journal-title":"Combinatorica"},{"key":"2026040314242756600_ref087","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0020-0190(00)00058-2","article-title":"A note on the use of determinant for proving lower bounds on the size of linear circuits","volume":"74","author":"Pudl\u00e1k","year":"2000","journal-title":"Inf. Process. Letters"},{"issue":"1-3","key":"2026040314242756600_ref088","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(94)00115-Y","article-title":"Some combinatorial-algebraic problems from complexity theory","volume":"136","author":"Pudl\u00e1k","year":"1994","journal-title":"Discrete Math."},{"issue":"5","key":"2026040314242756600_ref089","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF00279952","article-title":"Graph complexity","volume":"25","author":"Pudl\u00e1k","year":"1988","journal-title":"Acta Inf."},{"issue":"2","key":"2026040314242756600_ref090","first-page":"213","article-title":"Computation of rigidity of order n2\/r for one simple matrix","volume":"32","author":"Pudl\u00e1k","year":"1991","journal-title":"Comm. Math. Univ. Carol."},{"key":"2026040314242756600_ref091","article-title":"Entropy and counting","volume-title":"Manuscript","author":"Radhakrishnan","year":"2001"},{"issue":"1","key":"2026040314242756600_ref092","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1137\/S0895480197329508","article-title":"Bounds for dispersers, extractors, and depth-two superconcentrators","volume":"13","author":"Radhakrishnan","year":"2000","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"2026040314242756600_ref093","first-page":"598","article-title":"Lower bounds on the size of bounded-depth networks over a complete basis with logical addition","volume":"41","author":"Razborov","year":"1987","journal-title":"Mat. Zametki"},{"key":"2026040314242756600_ref094","doi-asserted-by":"crossref","first-page":"259","DOI":"10.4064\/aa-65-3-259-282","article-title":"Solving a linear equation in a set of integers. I","volume":"65","author":"Ruzsa","year":"1993","journal-title":"Acta Arith."},{"key":"2026040314242756600_ref095","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0304-3975(82)90113-X","article-title":"A family of graphs with expensive depth-reduction","volume":"18","author":"Schnitger","year":"1982","journal-title":"Theor. Comput. Sci."},{"key":"2026040314242756600_ref096","first-page":"323","article-title":"On depth-reduction and grates","volume-title":"24th IEEE Ann. Symp. on Foundations of Comput. Sci.","author":"Schnitger","year":"1983"},{"key":"2026040314242756600_ref097","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/BF00289470","article-title":"Schnelle multiplikation von Polynomen \u00fcber K\u00f6rpern der Charakteristik 2","volume":"7","author":"Sch\u00f6nhage","year":"1977","journal-title":"Acta Inf."},{"key":"2026040314242756600_ref098","first-page":"216","article-title":"Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables","volume-title":"Proc. of 11-th Int. Seminar on Discrete Math. and Its Appl.","author":"Selezneva","year":"2012"},{"key":"2026040314242756600_ref099","article-title":"Implementation of linear maps with circulant matrices via modulo 2 rectifier circuits of bounded depth","volume-title":"Technical report","author":"Sergeev","year":"2013"},{"issue":"3","key":"2026040314242756600_ref100","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1090\/S0002-9947-1938-1501951-4","article-title":"A theorem in finite projective geometry and some applications to number theory","volume":"43","author":"Singer","year":"1938","journal-title":"Trans. Amer. Math. Soc."},{"issue":"6","key":"2026040314242756600_ref101","doi-asserted-by":"crossref","first-page":"1723","DOI":"10.1109\/18.556668","article-title":"Linear-time encodable and decodable error-correcting codes","volume":"42","author":"Spielman","year":"1996","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026040314242756600_ref102","article-title":"Essential coding theory","volume-title":"Manuscript","author":"Sudan","year":"2002"},{"key":"2026040314242756600_ref103","first-page":"203","article-title":"Complexity of lattice-configurations","volume":"10","author":"Tarjan","year":"1975","journal-title":"Stud. Sci. Math. Hung."},{"issue":"1","key":"2026040314242756600_ref104","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02579163","article-title":"Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices","volume":"4","author":"Tuza","year":"1984","journal-title":"Combinatorica"},{"issue":"3","key":"2026040314242756600_ref105","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/S0022-0000(76)80041-4","article-title":"Graph-theoretic properties in computational complexity","volume":"13","author":"Valiant","year":"1976","journal-title":"J. Comput. Syst. Sci."},{"key":"2026040314242756600_ref106","first-page":"162","volume-title":"Springer Lect. Notes in Comput. Sci.","author":"Valiant","year":"1977"},{"key":"2026040314242756600_ref107","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF00288962","article-title":"A new lower bound on the monotone network complexity of Boolean sums","volume":"15","author":"Wegener","year":"1980","journal-title":"Acta Inform."},{"key":"2026040314242756600_ref108","volume-title":"The complexity of Boolean functions","author":"Wegener","year":"1987"},{"key":"2026040314242756600_ref109","volume-title":"Matroid theory","author":"Welsh","year":"1976"},{"key":"2026040314242756600_ref110","first-page":"665","volume-title":"Proceedings of the ICM 06 (Madrid)","author":"Wigderson","year":"2007"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/9\/1\/1\/11150375\/0400000063en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/9\/1\/1\/11150375\/0400000063en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:01:19Z","timestamp":1777489279000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/9\/1\/1\/1332205\/Complexity-of-Linear-Boolean-Operators"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,31]]},"references-count":110,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,10,31]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000063","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,31]]}}}