Ambainis, Andris; De Wolf, Ronald How low can approximate degree and quantum query complexity be for total Boolean functions? (English) Zbl 1314.68133 Comput. Complexity 23, No. 2, 305-322 (2014). MSC: 68Q12 06E30 41A10 68Q17 PDFBibTeX XMLCite \textit{A. Ambainis} and \textit{R. De Wolf}, Comput. Complexity 23, No. 2, 305--322 (2014; Zbl 1314.68133) Full Text: DOI arXiv
Mundhenk, Martin; Wei, Felix An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic. (English) Zbl 1522.68336 Comput. Complexity 23, No. 4, 637-669 (2014). MSC: 68Q60 03B20 06D20 68Q17 PDFBibTeX XMLCite \textit{M. Mundhenk} and \textit{F. Wei}, Comput. Complexity 23, No. 4, 637--669 (2014; Zbl 1522.68336) Full Text: DOI
Diakonikolas, Ilias; Servedio, Rocco A. Improved approximation of linear threshold functions. (English) Zbl 1273.68292 Comput. Complexity 22, No. 3, 623-677 (2013). MSC: 68R99 06E30 28A35 PDFBibTeX XMLCite \textit{I. Diakonikolas} and \textit{R. A. Servedio}, Comput. Complexity 22, No. 3, 623--677 (2013; Zbl 1273.68292) Full Text: DOI
Servedio, Rocco A. Every linear threshold function has a low-weight approximator. (English) Zbl 1128.68043 Comput. Complexity 16, No. 2, 180-209 (2007). MSC: 68Q32 06E30 52C07 68Q17 90C27 PDFBibTeX XMLCite \textit{R. A. Servedio}, Comput. Complexity 16, No. 2, 180--209 (2007; Zbl 1128.68043) Full Text: DOI
Kára, Jan; Král’, Daniel Free binary decision diagrams for the computation of \(\text{EAR}_{ n }\). (English) Zbl 1110.68044 Comput. Complexity 15, No. 1, 40-61 (2006). MSC: 68Q05 06E30 68P05 68Q25 PDFBibTeX XMLCite \textit{J. Kára} and \textit{D. Král'}, Comput. Complexity 15, No. 1, 40--61 (2006; Zbl 1110.68044) Full Text: DOI
Krause, Matthias On the computational power of Boolean decision lists. (English) Zbl 1105.68043 Comput. Complexity 14, No. 4, 362-375 (2005). MSC: 68Q15 68Q17 68Q32 94C10 06E30 PDFBibTeX XMLCite \textit{M. Krause}, Comput. Complexity 14, No. 4, 362--375 (2005; Zbl 1105.68043) Full Text: DOI
Meinel, Christoph; Waack, Stephan The ”log rank” conjecture for modular communication complexity. (English) Zbl 0998.68065 Comput. Complexity 10, No. 1, 70-91 (2001). MSC: 68Q15 68Q17 94C10 06E30 PDFBibTeX XMLCite \textit{C. Meinel} and \textit{S. Waack}, Comput. Complexity 10, No. 1, 70--91 (2001; Zbl 0998.68065) Full Text: DOI
Chockler, Hana; Zwick, Uri Which bases admit non-trivial shrinkage of formulae? (English) Zbl 0988.06009 Comput. Complexity 10, No. 1, 28-40 (2001). MSC: 06E30 68Q17 03D15 94C10 PDFBibTeX XMLCite \textit{H. Chockler} and \textit{U. Zwick}, Comput. Complexity 10, No. 1, 28--40 (2001; Zbl 0988.06009) Full Text: DOI
Krause, Matthias; Pudlák, Pavel Computing Boolean functions by polynomials and threshold circuits. (English) Zbl 0936.94022 Comput. Complexity 7, No. 4, 346-370 (1998). Reviewer: I.Strazdins (Riga) MSC: 94C10 06E30 60E05 PDFBibTeX XMLCite \textit{M. Krause} and \textit{P. Pudlák}, Comput. Complexity 7, No. 4, 346--370 (1998; Zbl 0936.94022) Full Text: DOI
Bruck, Jehoshua Reflections on “Representations of sets of Boolean functions by commutative rings” by Roman Smolensky. (English) Zbl 0890.68062 Comput. Complexity 6(1996-97), No. 3, 209-212 (1997). MSC: 68Q15 68R99 06E30 PDFBibTeX XMLCite \textit{J. Bruck}, Comput. Complexity 6, No. 3, 209--212 (1997; Zbl 0890.68062) Full Text: DOI
Smolensky, Roman Representations of sets of Boolean functions by commutative rings. (English) Zbl 0890.68061 Comput. Complexity 6(1996-97), No. 3, 199-208 (1997). MSC: 68Q15 06E30 PDFBibTeX XMLCite \textit{R. Smolensky}, Comput. Complexity 6, No. 3, 199--208 (1997; Zbl 0890.68061) Full Text: DOI
Bshouty, Nader H. Simple learning algorithms using divide and conquer. (English) Zbl 0868.68094 Comput. Complexity 6, No. 2, 174-194 (1997). MSC: 68T05 06E30 68Q25 PDFBibTeX XMLCite \textit{N. H. Bshouty}, Comput. Complexity 6, No. 2, 174--194 (1997; Zbl 0868.68094) Full Text: DOI
Paterson, Michael; Zwick, Uri Shallow circuits and concise formulae for multiple addition and multiplication. (English) Zbl 0801.68092 Comput. Complexity 3, No. 3, 262-291 (1993). MSC: 68W35 68Q25 94C10 06E30 PDFBibTeX XMLCite \textit{M. Paterson} and \textit{U. Zwick}, Comput. Complexity 3, No. 3, 262--291 (1993; Zbl 0801.68092) Full Text: DOI
Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell Exponential lower bounds for the pigeonhole principle. (English) Zbl 0784.03034 Comput. Complexity 3, No. 2, 97-140 (1993). Reviewer: P.Jančar (Ostrava) MSC: 03F20 68Q99 68R05 06E30 PDFBibTeX XMLCite \textit{T. Pitassi} et al., Comput. Complexity 3, No. 2, 97--140 (1993; Zbl 0784.03034) Full Text: DOI
Heiman, Rafi; Wigderson, Avi Randomized vs. deterministic decision tree complexity for read-once Boolean functions. (English) Zbl 0774.68061 Comput. Complexity 1, No. 4, 311-329 (1991). MSC: 68Q25 06E30 94D10 PDFBibTeX XMLCite \textit{R. Heiman} and \textit{A. Wigderson}, Comput. Complexity 1, No. 4, 311--329 (1991; Zbl 0774.68061) Full Text: DOI