Martin, Jo; Rombach, Puck Guessing numbers and extremal graph theory. (English) Zbl 1492.05074 Electron. J. Comb. 29, No. 2, Research Paper P2.58, 16 p. (2022). MSC: 05C35 05C15 60C05 94A17 PDFBibTeX XMLCite \textit{J. Martin} and \textit{P. Rombach}, Electron. J. Comb. 29, No. 2, Research Paper P2.58, 16 p. (2022; Zbl 1492.05074) Full Text: DOI arXiv
Oliveira, Igor C.; Santhanam, Rahul; Tell, Roei Expander-based cryptography meets natural proofs. (English) Zbl 07506816 Comput. Complexity 31, No. 1, Paper No. 4, 60 p. (2022). MSC: 68Q06 94A60 PDFBibTeX XMLCite \textit{I. C. Oliveira} et al., Comput. Complexity 31, No. 1, Paper No. 4, 60 p. (2022; Zbl 07506816) Full Text: DOI
Babai, László; Hansen, Kristoffer A.; Podolskii, Vladimir V.; Sun, Xiaoming Weights of exact threshold functions. (English. Russian original) Zbl 1492.94224 Izv. Math. 85, No. 6, 1039-1059 (2021); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 85, No. 6, 5-26 (2021). MSC: 94C11 94D10 68Q15 PDFBibTeX XMLCite \textit{L. Babai} et al., Izv. Math. 85, No. 6, 1039--1059 (2021; Zbl 1492.94224); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 85, No. 6, 5--26 (2021) Full Text: DOI MNR
Williams, R. Ryan From circuit complexity to faster all-pairs shortest paths. (English) Zbl 1470.05139 SIAM Rev. 63, No. 3, 559-582 (2021). MSC: 05C76 05C82 05C85 68Q25 94C05 68W25 PDFBibTeX XMLCite \textit{R. R. Williams}, SIAM Rev. 63, No. 3, 559--582 (2021; Zbl 1470.05139) Full Text: DOI
Chee, Yeow Meng; Colbourn, Charles J.; Dau, Hoang; Gabrys, Ryan; Ling, Alan C. H.; Lusi, Dylan; Milenkovic, Olgica Access balancing in storage systems by labeling partial Steiner systems. (English) Zbl 1457.05014 Des. Codes Cryptography 88, No. 11, 2361-2376 (2020). MSC: 05B07 05B40 94B60 68P20 PDFBibTeX XMLCite \textit{Y. M. Chee} et al., Des. Codes Cryptography 88, No. 11, 2361--2376 (2020; Zbl 1457.05014) Full Text: DOI arXiv
Amano, Kazuyuki; Tate, Shoma On XOR lemmas for the weight of polynomial threshold functions. (English) Zbl 1435.68220 Inf. Comput. 269, Article ID 104439, 11 p. (2019). MSC: 68R05 06E30 68Q25 90C10 94D10 PDFBibTeX XMLCite \textit{K. Amano} and \textit{S. Tate}, Inf. Comput. 269, Article ID 104439, 11 p. (2019; Zbl 1435.68220) Full Text: DOI
Sakai, Takayuki; Seto, Kazuhisa; Tamaki, Suguru; Teruyama, Junichi Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression. (English) Zbl 1423.68218 J. Comput. Syst. Sci. 105, 87-103 (2019). MSC: 68Q25 68Q17 94C10 PDFBibTeX XMLCite \textit{T. Sakai} et al., J. Comput. Syst. Sci. 105, 87--103 (2019; Zbl 1423.68218) Full Text: DOI Link
Chen, Shiteng; Papakonstantinou, Periklis A. Depth reduction for composites. (English) Zbl 1421.68054 SIAM J. Comput. 48, No. 2, 668-686 (2019). MSC: 68Q15 68Q17 94C10 PDFBibTeX XMLCite \textit{S. Chen} and \textit{P. A. Papakonstantinou}, SIAM J. Comput. 48, No. 2, 668--686 (2019; Zbl 1421.68054) Full Text: DOI
Cheraghchi, Mahdi; Grigorescu, Elena; Juba, Brendan; Wimmer, Karl; Xie, Ning \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product. (English) Zbl 1398.68159 J. Comput. Syst. Sci. 97, 45-59 (2018). MSC: 68Q05 68Q17 94C10 PDFBibTeX XMLCite \textit{M. Cheraghchi} et al., J. Comput. Syst. Sci. 97, 45--59 (2018; Zbl 1398.68159) Full Text: DOI
Kawachi, Akinori Circuit lower bounds from learning-theoretic approaches. (English) Zbl 1393.68152 Theor. Comput. Sci. 733, 83-98 (2018). MSC: 68T05 68Q17 94C10 PDFBibTeX XMLCite \textit{A. Kawachi}, Theor. Comput. Sci. 733, 83--98 (2018; Zbl 1393.68152) Full Text: DOI
Hansen, Kristoffer Arnsfelt; Podolskii, Vladimir V. Polynomial threshold functions and Boolean threshold circuits. (English) Zbl 1312.68089 Inf. Comput. 240, 56-73 (2015). MSC: 68Q15 94C10 PDFBibTeX XMLCite \textit{K. A. Hansen} and \textit{V. V. Podolskii}, Inf. Comput. 240, 56--73 (2015; Zbl 1312.68089) Full Text: DOI
Annampedu, Viswanath; Wagh, Meghanad D. Decomposition of threshold functions into bounded fan-in threshold functions. (English) Zbl 1358.94114 Inf. Comput. 227, 84-101 (2013). MSC: 94C10 PDFBibTeX XMLCite \textit{V. Annampedu} and \textit{M. D. Wagh}, Inf. Comput. 227, 84--101 (2013; Zbl 1358.94114) Full Text: DOI
Podolskii, Vladimir V. Degree-uniform lower bound on the weights of polynomials with given sign function. (English. Russian original) Zbl 1358.94116 Proc. Steklov Inst. Math. 274, 231-246 (2011); translation from Tr. Mat. Inst. Steklova 274, 252-268 (2011). MSC: 94C10 68Q17 PDFBibTeX XMLCite \textit{V. V. Podolskii}, Proc. Steklov Inst. Math. 274, 231--246 (2011; Zbl 1358.94116); translation from Tr. Mat. Inst. Steklova 274, 252--268 (2011) Full Text: DOI
Podolskii, V. V.; Sherstov, A. A. A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length. (English. Russian original) Zbl 1317.94168 Math. Notes 87, No. 6, 860-873 (2010); translation from Mat. Zametki 87, No. 6, 886-900 (2010). MSC: 94C10 06E30 PDFBibTeX XMLCite \textit{V. V. Podolskii} and \textit{A. A. Sherstov}, Math. Notes 87, No. 6, 860--873 (2010; Zbl 1317.94168); translation from Mat. Zametki 87, No. 6, 886--900 (2010) Full Text: DOI
Uchizawa, Kei; Takimoto, Eiji Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity. (English) Zbl 1152.68047 Theor. Comput. Sci. 407, No. 1-3, 474-487 (2008). MSC: 68T05 68Q17 92B20 94C10 PDFBibTeX XMLCite \textit{K. Uchizawa} and \textit{E. Takimoto}, Theor. Comput. Sci. 407, No. 1--3, 474--487 (2008; Zbl 1152.68047) Full Text: DOI
Uchizawa, Kei; Douglas, Rodney; Maass, Wolfgang On the computational power of threshold circuits with sparse activity. (English) Zbl 1104.92003 Neural Comput. 18, No. 12, 2994-3008 (2006). MSC: 92B20 94C99 92C20 68T05 PDFBibTeX XMLCite \textit{K. Uchizawa} et al., Neural Comput. 18, No. 12, 2994--3008 (2006; Zbl 1104.92003) Full Text: DOI
Kiltz, Eike; Simon, Hans Ulrich Threshold circuit lower bounds on cryptographic functions. (English) Zbl 1078.68033 J. Comput. Syst. Sci. 71, No. 2, 185-212 (2005). MSC: 68P25 94A60 PDFBibTeX XMLCite \textit{E. Kiltz} and \textit{H. U. Simon}, J. Comput. Syst. Sci. 71, No. 2, 185--212 (2005; Zbl 1078.68033) Full Text: DOI
Bourgain, Jean Estimation of certain exponential sums arising in complexity theory. (English. Abridged French version) Zbl 1112.11038 C. R., Math., Acad. Sci. Paris 340, No. 9, 627-631 (2005). MSC: 11L07 68Q15 94C10 PDFBibTeX XMLCite \textit{J. Bourgain}, C. R., Math., Acad. Sci. Paris 340, No. 9, 627--631 (2005; Zbl 1112.11038) Full Text: DOI
Fraigniaud, Pierre; Peters, Joseph G. Minimum linear gossip graphs and maximal linear \((\Delta,k)\)-gossip graphs. (English) Zbl 0993.94026 Networks 38, No. 3, 150-162 (2001). Reviewer: Wai Kai Chen (Chicago) MSC: 94C15 05C35 PDFBibTeX XMLCite \textit{P. Fraigniaud} and \textit{J. G. Peters}, Networks 38, No. 3, 150--162 (2001; Zbl 0993.94026) Full Text: DOI
Maciel, Alexis; Thérien, Denis Efficient threshold circuits for power series. (English) Zbl 1009.68061 Inf. Comput. 152, No. 1, 62-73 (1999). MSC: 68Q25 94C10 68Q15 PDFBibTeX XMLCite \textit{A. Maciel} and \textit{D. Thérien}, Inf. Comput. 152, No. 1, 62--73 (1999; Zbl 1009.68061) Full Text: DOI
Grolmusz, Vince A lower bound for depth-3 circuits with MOD \(m\) gates. (English) Zbl 1338.68106 Inf. Process. Lett. 67, No. 2, 87-90 (1998). MSC: 68Q25 68Q05 68W20 94C10 PDFBibTeX XMLCite \textit{V. Grolmusz}, Inf. Process. Lett. 67, No. 2, 87--90 (1998; Zbl 1338.68106) Full Text: DOI Link
Fraigniaud, Pierre; Lazard, Emmanuel Methods and problems of communication in usual networks. (English) Zbl 0818.94029 Discrete Appl. Math. 53, No. 1-3, 79-133 (1994). Reviewer: M.Middendorf (Karlsruhe) MSC: 94C15 94-02 94A05 05C90 PDFBibTeX XMLCite \textit{P. Fraigniaud} and \textit{E. Lazard}, Discrete Appl. Math. 53, No. 1--3, 79--133 (1994; Zbl 0818.94029) Full Text: DOI
Feldmann, R.; Hromkovič, Juraj; Madhavapeddy, S.; Monien, B.; Mysliwietz, P. Optimal algorithms for dissemination of information in generalized communication modes. (English) Zbl 0823.68041 Discrete Appl. Math. 53, No. 1-3, 55-78 (1994). MSC: 68Q25 05C90 68R10 94C15 PDFBibTeX XMLCite \textit{R. Feldmann} et al., Discrete Appl. Math. 53, No. 1--3, 55--78 (1994; Zbl 0823.68041) Full Text: DOI
Lee, Hsun-Ming; Chang, Gerard J. Set to set broadcasting in communication networks. (English) Zbl 0765.94027 Discrete Appl. Math. 40, No. 3, 411-421 (1992). MSC: 94C15 94A05 PDFBibTeX XMLCite \textit{H.-M. Lee} and \textit{G. J. Chang}, Discrete Appl. Math. 40, No. 3, 411--421 (1992; Zbl 0765.94027) Full Text: DOI
Haddad, Ramsey W.; Roy, Shaibal; Schäffer, Alejandro A. On gossiping with faulty telephone lines. (English) Zbl 0626.05033 SIAM J. Algebraic Discrete Methods 8, 439-445 (1987). MSC: 05C38 94C15 PDFBibTeX XMLCite \textit{R. W. Haddad} et al., SIAM J. Algebraic Discrete Methods 8, 439--445 (1987; Zbl 0626.05033) Full Text: DOI
Seress, Ákos Quick gossiping without duplicate transmissions. (English) Zbl 0601.05029 Graphs Comb. 2, 363-381 (1986). MSC: 05C38 94A05 05C99 PDFBibTeX XMLCite \textit{Á. Seress}, Graphs Comb. 2, 363--381 (1986; Zbl 0601.05029) Full Text: DOI
Berman, Kenneth A.; Hawrylycz, Michael Telephone problems with failures. (English) Zbl 0578.05059 SIAM J. Algebraic Discrete Methods 7, 13-17 (1986). MSC: 05C35 90B10 94C15 PDFBibTeX XMLCite \textit{K. A. Berman} and \textit{M. Hawrylycz}, SIAM J. Algebraic Discrete Methods 7, 13--17 (1986; Zbl 0578.05059) Full Text: DOI
Liestman, Arthur L.; Richards, Dana Toward optimal gossiping schemes with conference calls. (English) Zbl 0529.05043 Discrete Appl. Math. 7, 183-189 (1984). MSC: 05C65 05C35 94A99 PDFBibTeX XMLCite \textit{A. L. Liestman} and \textit{D. Richards}, Discrete Appl. Math. 7, 183--189 (1984; Zbl 0529.05043) Full Text: DOI
Assmann, Susan F.; Kleitman, Daniel J. The number of rounds needed to exchange information within a graph. (English) Zbl 0519.05044 Discrete Appl. Math. 6, 117-125 (1983). MSC: 05C35 05C99 94A99 PDFBibTeX XMLCite \textit{S. F. Assmann} and \textit{D. J. Kleitman}, Discrete Appl. Math. 6, 117--125 (1983; Zbl 0519.05044) Full Text: DOI
West, Douglas B. A class of solutions to the gossip problem. I. (English) Zbl 0497.05037 Discrete Math. 39, 307-326 (1982). MSC: 05C38 94A05 05C99 05C75 05C70 PDFBibTeX XMLCite \textit{D. B. West}, Discrete Math. 39, 307--326 (1982; Zbl 0497.05037) Full Text: DOI