Chu, Timothy; Gao, Yu; Peng, Richard; Sachdeva, Sushant; Sawlani, Saurabh; Wang, Junxing Graph sparsification, spectral sketches, and faster resistance computation via short cycle decompositions. (English) Zbl 07780703 SIAM J. Comput. 52, No. 6, FOCS18-85-FOCS18-157 (2023). MSC: 68W25 05C85 PDFBibTeX XMLCite \textit{T. Chu} et al., SIAM J. Comput. 52, No. 6, FOCS18--85-FOCS18--157 (2023; Zbl 07780703) Full Text: DOI arXiv
Gharibian, Sevag; Le Gall, François Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum PCP conjecture. (English) Zbl 1520.68041 SIAM J. Comput. 52, No. 4, 1009-1038 (2023). MSC: 68Q12 68Q17 81P68 81V55 PDFBibTeX XMLCite \textit{S. Gharibian} and \textit{F. Le Gall}, SIAM J. Comput. 52, No. 4, 1009--1038 (2023; Zbl 1520.68041) Full Text: DOI arXiv
Bhattacharyya, Arnab; Gayen, Sutanu; Price, Eric; Tan, Vincent Y. F.; Vinodchandran, N. V. Near-optimal learning of tree-structured distributions by Chow and Liu. (English) Zbl 07707672 SIAM J. Comput. 52, No. 3, 761-793 (2023). MSC: 68Q32 68W20 94A15 PDFBibTeX XMLCite \textit{A. Bhattacharyya} et al., SIAM J. Comput. 52, No. 3, 761--793 (2023; Zbl 07707672) Full Text: DOI arXiv
Davies, Ewan; Perkins, Will Approximately counting independent sets of a given size in bounded-degree graphs. (English) Zbl 07680602 SIAM J. Comput. 52, No. 2, 618-640 (2023). MSC: 68Q17 68Q25 68Q87 05C30 PDFBibTeX XMLCite \textit{E. Davies} and \textit{W. Perkins}, SIAM J. Comput. 52, No. 2, 618--640 (2023; Zbl 07680602) Full Text: DOI arXiv
Grochow, Joshua; Qiao, Youming On the complexity of isomorphism problems for tensors, groups, and polynomials. I: Tensor isomorphism-completeness. (English) Zbl 07680601 SIAM J. Comput. 52, No. 2, 568-617 (2023). MSC: 68Q15 81P45 68Q17 PDFBibTeX XMLCite \textit{J. Grochow} and \textit{Y. Qiao}, SIAM J. Comput. 52, No. 2, 568--617 (2023; Zbl 07680601) Full Text: DOI
Chen, Zongchen; Liu, Kuikui; Vigoda, Eric Rapid mixing of Glauber dynamics up to uniqueness via contraction. (English) Zbl 07672228 SIAM J. Comput. 52, No. 1, 196-237 (2023). MSC: 82C20 82B05 82C26 68Q87 68W20 60J10 PDFBibTeX XMLCite \textit{Z. Chen} et al., SIAM J. Comput. 52, No. 1, 196--237 (2023; Zbl 07672228) Full Text: DOI arXiv
Kaplan, Haim; Mansour, Yishay; Matias, Yossi; Stemmer, Uri Differentially private learning of geometric concepts. (English) Zbl 1499.68310 SIAM J. Comput. 51, No. 4, 952-974 (2022). MSC: 68T05 68P27 68U05 PDFBibTeX XMLCite \textit{H. Kaplan} et al., SIAM J. Comput. 51, No. 4, 952--974 (2022; Zbl 1499.68310) Full Text: DOI arXiv
Dell, Holger; Lapinskas, John; Meeks, Kitty Approximately counting and sampling small witnesses using a colorful decision oracle. (English) Zbl 1502.68220 SIAM J. Comput. 51, No. 4, 849-899 (2022). MSC: 68R10 05C65 68Q27 68W20 68W25 PDFBibTeX XMLCite \textit{H. Dell} et al., SIAM J. Comput. 51, No. 4, 849--899 (2022; Zbl 1502.68220) Full Text: DOI
Brakensiek, Joshua; Gopi, Sivakanth; Guruswami, Venkatesan Constraint satisfaction problems with global modular constraints: algorithms and hardness via polynomial representations. (English) Zbl 07538272 SIAM J. Comput. 51, No. 3, 577-626 (2022). MSC: 68Q25 94B05 20K01 68W20 08A70 03B70 12Y05 PDFBibTeX XMLCite \textit{J. Brakensiek} et al., SIAM J. Comput. 51, No. 3, 577--626 (2022; Zbl 07538272) Full Text: DOI
Bernardini, Giulia; Gawrychowski, Paweł; Pisanti, Nadia; Pissis, Solon P.; Rosone, Giovanna Elastic-degenerate string matching via fast matrix multiplication. (English) Zbl 07538271 SIAM J. Comput. 51, No. 3, 549-576 (2022). MSC: 68W01 68W32 68Q25 68Q17 PDFBibTeX XMLCite \textit{G. Bernardini} et al., SIAM J. Comput. 51, No. 3, 549--576 (2022; Zbl 07538271) Full Text: DOI arXiv
Asharov, Gilad; Lin, Wei-Kai; Shi, Elaine Sorting short keys in circuits of size \(o(n\log n)\). (English) Zbl 07534657 SIAM J. Comput. 51, No. 3, 424-466 (2022). MSC: 68W01 PDFBibTeX XMLCite \textit{G. Asharov} et al., SIAM J. Comput. 51, No. 3, 424--466 (2022; Zbl 07534657) Full Text: DOI arXiv
Cai, Jin-Yi; Fu, Zhiguo Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. (English) Zbl 07516618 SIAM J. Comput. 51, No. 2, STOC17-50-STOC17-151 (2022). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{Z. Fu}, SIAM J. Comput. 51, No. 2, STOC17--50-STOC17--151 (2022; Zbl 07516618) Full Text: DOI
Roth, Marc; Schmitt, Johannes; Wellnitz, Philip Counting small induced subgraphs satisfying monotone properties. (English) Zbl 07510283 SIAM J. Comput. 51, No. 2, FOCS20-139-FOCS20-174 (2022). MSC: 68Q27 68Q17 05E40 PDFBibTeX XMLCite \textit{M. Roth} et al., SIAM J. Comput. 51, No. 2, FOCS20--139-FOCS20--174 (2022; Zbl 07510283) Full Text: DOI arXiv
Alman, Josh; Chen, Lijie Efficient construction of rigid matrices using an NP oracle. (English) Zbl 07488095 SIAM J. Comput. 51, No. 1, FOCS19-102-FOCS19-134 (2022). MSC: 68Q05 68Q17 PDFBibTeX XMLCite \textit{J. Alman} and \textit{L. Chen}, SIAM J. Comput. 51, No. 1, FOCS19--102-FOCS19--134 (2022; Zbl 07488095) Full Text: DOI
Bhandari, Siddharth; Chakraborty, Sayantan Improved bounds for perfect sampling of \(k\)-colorings in graphs. (English) Zbl 1482.05096 SIAM J. Comput. 51, No. 3, STOC20-54-STOC20-74 (2022). MSC: 05C15 60J10 60J22 68W20 PDFBibTeX XMLCite \textit{S. Bhandari} and \textit{S. Chakraborty}, SIAM J. Comput. 51, No. 3, STOC20--54-STOC20--74 (2022; Zbl 1482.05096) Full Text: DOI
Backens, Miriam A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation. (English) Zbl 1492.68101 SIAM J. Comput. 50, No. 6, 1739-1799 (2021). MSC: 68R10 68Q25 81P40 81P45 81P68 PDFBibTeX XMLCite \textit{M. Backens}, SIAM J. Comput. 50, No. 6, 1739--1799 (2021; Zbl 1492.68101) Full Text: DOI arXiv
Anari, Nima; Rezaei, Alireza A tight analysis of Bethe approximation for permanent. (English) Zbl 07453416 SIAM J. Comput. 50, No. 5, FOCS19-81-FOCS19-101 (2021). MSC: 68Q25 15A15 68W25 PDFBibTeX XMLCite \textit{N. Anari} and \textit{A. Rezaei}, SIAM J. Comput. 50, No. 5, FOCS19--81-FOCS19--101 (2021; Zbl 07453416) Full Text: DOI arXiv
Boix-Adserà, Enric; Brennan, Matthew; Bresler, Guy The average-case complexity of counting cliques in Erdös-Rényi hypergraphs. (English) Zbl 1528.68276 SIAM J. Comput. 50, No. 5, FOCS19-39-FOCS19-80 (2021). MSC: 68R10 05C65 05C80 05C85 68Q25 PDFBibTeX XMLCite \textit{E. Boix-Adserà} et al., SIAM J. Comput. 50, No. 5, FOCS19--39-FOCS19--80 (2021; Zbl 1528.68276) Full Text: DOI arXiv
Anari, Nima; Liu, Kuikui; Gharan, Shayan Oveis Spectral independence in high-dimensional expanders and applications to the hardcore model. (English) Zbl 1522.05449 SIAM J. Comput. 50, No. 4, FOCS20-1-FOCS20-37 (2021). MSC: 05C81 05C48 05E45 82C20 PDFBibTeX XMLCite \textit{N. Anari} et al., SIAM J. Comput. 50, No. 4, FOCS20--1-FOCS20--37 (2021; Zbl 1522.05449) Full Text: DOI arXiv
Reingold, Omer; Rothblum, Guy N.; Rothblum, Ron D. Constant-round interactive proofs for delegating computation. (English) Zbl 1464.68128 SIAM J. Comput. 50, No. 3, STOC16-255-STOC16-340 (2021). MSC: 68Q25 68Q10 68Q17 PDFBibTeX XMLCite \textit{O. Reingold} et al., SIAM J. Comput. 50, No. 3, STOC16--255-STOC16--340 (2021; Zbl 1464.68128) Full Text: DOI
Eppstein, David; Vazirani, Vijay V. NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs. (English) Zbl 1466.05179 SIAM J. Comput. 50, No. 3, 1014-1033 (2021). MSC: 05C70 05C83 05C21 68W10 68R10 PDFBibTeX XMLCite \textit{D. Eppstein} and \textit{V. V. Vazirani}, SIAM J. Comput. 50, No. 3, 1014--1033 (2021; Zbl 1466.05179) Full Text: DOI arXiv
Arunachalam, Srinivasan; Grilo, Alex Bredariol; Sundaram, Aarthi Quantum hardness of learning shallow classical circuits. (English) Zbl 1516.68037 SIAM J. Comput. 50, No. 3, 972-1013 (2021). MSC: 68Q12 68Q06 68T05 81P68 81P94 PDFBibTeX XMLCite \textit{S. Arunachalam} et al., SIAM J. Comput. 50, No. 3, 972--1013 (2021; Zbl 1516.68037) Full Text: DOI arXiv
Feng, Weiming; Vishnoi, Nisheeth K.; Yin, Yitong Dynamic sampling from graphical models. (English) Zbl 1509.62264 SIAM J. Comput. 50, No. 2, 350-381 (2021). MSC: 62H22 62D05 62-08 PDFBibTeX XMLCite \textit{W. Feng} et al., SIAM J. Comput. 50, No. 2, 350--381 (2021; Zbl 1509.62264) Full Text: DOI
Chattopadhyay, Arkadev; Filmus, Yuval; Koroth, Sajin; Meir, Or; Pitassi, Toniann Query-to-communication lifting using low-discrepancy gadgets. (English) Zbl 1509.68086 SIAM J. Comput. 50, No. 1, 171-210 (2021). MSC: 68Q11 PDFBibTeX XMLCite \textit{A. Chattopadhyay} et al., SIAM J. Comput. 50, No. 1, 171--210 (2021; Zbl 1509.68086) Full Text: DOI arXiv
Aaronson, Scott Shadow tomography of quantum states. (English) Zbl 1503.81014 SIAM J. Comput. 49, No. 5, STOC18-368-STOC18-394 (2020). MSC: 81P68 68Q12 81P45 81P16 81P15 81P50 PDFBibTeX XMLCite \textit{S. Aaronson}, SIAM J. Comput. 49, No. 5, STOC18--368-STOC18--394 (2020; Zbl 1503.81014) Full Text: DOI
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel Inapproximability of the independent set polynomial in the complex plane. (English) Zbl 1476.68193 SIAM J. Comput. 49, No. 5, STOC18-395-STOC18-448 (2020). MSC: 68R10 05C31 05C69 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{I. Bezáková} et al., SIAM J. Comput. 49, No. 5, STOC18--395-STOC18--448 (2020; Zbl 1476.68193) Full Text: DOI
Björklund, Andreas; Husfeldt, Thore Shortest two disjoint paths in polynomial time. (English) Zbl 1428.05292 SIAM J. Comput. 48, No. 6, 1698-1710 (2019). MSC: 05C85 05C38 05C12 68W20 PDFBibTeX XMLCite \textit{A. Björklund} and \textit{T. Husfeldt}, SIAM J. Comput. 48, No. 6, 1698--1710 (2019; Zbl 1428.05292) Full Text: DOI
Guo, Heng; Liao, Chao; Lu, Pinyan; Zhang, Chihao Counting hypergraph colorings in the local lemma regime. (English) Zbl 1430.68447 SIAM J. Comput. 48, No. 4, 1397-1424 (2019). MSC: 68W25 05C15 05C30 05C65 PDFBibTeX XMLCite \textit{H. Guo} et al., SIAM J. Comput. 48, No. 4, 1397--1424 (2019; Zbl 1430.68447) Full Text: DOI arXiv
van Melkebeek, Dieter; Prakriya, Gautam Derandomizing isolation in space-bounded settings. (English) Zbl 1430.68109 SIAM J. Comput. 48, No. 3, 979-1021 (2019). MSC: 68Q04 68Q10 68Q15 68Q25 68R10 PDFBibTeX XMLCite \textit{D. van Melkebeek} and \textit{G. Prakriya}, SIAM J. Comput. 48, No. 3, 979--1021 (2019; Zbl 1430.68109) Full Text: DOI
Guo, Heng; Jerrum, Mark A polynomial-time approximation algorithm for all-terminal network reliability. (English) Zbl 1430.68441 SIAM J. Comput. 48, No. 3, 964-978 (2019). MSC: 68W20 68R10 68W25 68W40 PDFBibTeX XMLCite \textit{H. Guo} and \textit{M. Jerrum}, SIAM J. Comput. 48, No. 3, 964--978 (2019; Zbl 1430.68441) Full Text: DOI arXiv
Bringmann, Karl; Grandoni, Fabrizio; Saha, Barna; Williams, Virginia Vassilevska Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product. (English) Zbl 1421.68258 SIAM J. Comput. 48, No. 2, 481-512 (2019). MSC: 68W40 68W32 92D20 PDFBibTeX XMLCite \textit{K. Bringmann} et al., SIAM J. Comput. 48, No. 2, 481--512 (2019; Zbl 1421.68258) Full Text: DOI arXiv
Kumar, Mrinal; Saptharishi, Ramprasad The computational power of depth five arithmetic circuits. (English) Zbl 1417.68056 SIAM J. Comput. 48, No. 1, 144-180 (2019). MSC: 68Q17 12Y05 PDFBibTeX XMLCite \textit{M. Kumar} and \textit{R. Saptharishi}, SIAM J. Comput. 48, No. 1, 144--180 (2019; Zbl 1417.68056) Full Text: DOI
Chillara, Suryajith; Limaye, Nutan; Srinivasan, Srikanth Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications. (English) Zbl 1412.68069 SIAM J. Comput. 48, No. 1, 70-92 (2019). MSC: 68Q17 15A99 68Q25 PDFBibTeX XMLCite \textit{S. Chillara} et al., SIAM J. Comput. 48, No. 1, 70--92 (2019; Zbl 1412.68069) Full Text: DOI
Abboud, Amir; Backurs, Arturs; Williams, Virginia Vassilevska If the current clique algorithms are optimal, so is Valiant’s parser. (English) Zbl 1412.68094 SIAM J. Comput. 47, No. 6, 2527-2555 (2018). Reviewer: Andreas Maletti (Leipzig) MSC: 68Q42 05C69 68Q17 68Q25 68Q45 92D20 PDFBibTeX XMLCite \textit{A. Abboud} et al., SIAM J. Comput. 47, No. 6, 2527--2555 (2018; Zbl 1412.68094) Full Text: DOI arXiv
Cohen, Aloni; Holmgren, Justin; Nishimaki, Ryo; Vaikuntanathan, Vinod; Wichs, Daniel Watermarking cryptographic capabilities. (English) Zbl 1443.94052 SIAM J. Comput. 47, No. 6, 2157-2202 (2018). MSC: 94A60 PDFBibTeX XMLCite \textit{A. Cohen} et al., SIAM J. Comput. 47, No. 6, 2157--2202 (2018; Zbl 1443.94052) Full Text: DOI
Lin, Jiabao; Wang, Hanpin The complexity of Boolean Holant problems with nonnegative weights. (English) Zbl 1397.68105 SIAM J. Comput. 47, No. 3, 798-828 (2018). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{J. Lin} and \textit{H. Wang}, SIAM J. Comput. 47, No. 3, 798--828 (2018; Zbl 1397.68105) Full Text: DOI
Balcan, Maria-Florina; Harvey, Nicholas J. A. Submodular functions: learnability, structure, and optimization. (English) Zbl 1395.68228 SIAM J. Comput. 47, No. 3, 703-754 (2018). MSC: 68T05 05B35 90C27 91A26 PDFBibTeX XMLCite \textit{M.-F. Balcan} and \textit{N. J. A. Harvey}, SIAM J. Comput. 47, No. 3, 703--754 (2018; Zbl 1395.68228) Full Text: DOI arXiv
Huang, Zhiyi; Mansour, Yishay; Roughgarden, Tim Making the most of your samples. (English) Zbl 1390.91146 SIAM J. Comput. 47, No. 3, 651-674 (2018). MSC: 91B26 68Q25 PDFBibTeX XMLCite \textit{Z. Huang} et al., SIAM J. Comput. 47, No. 3, 651--674 (2018; Zbl 1390.91146) Full Text: DOI arXiv
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji Holographic algorithms with matchgates capture precisely tractable planar #CSP. (English) Zbl 1370.68117 SIAM J. Comput. 46, No. 3, 853-889 (2017). MSC: 68Q25 68Q05 68Q17 68R10 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., SIAM J. Comput. 46, No. 3, 853--889 (2017; Zbl 1370.68117) Full Text: DOI arXiv
Kumar, Mrinal; Saraf, Shubhangi On the power of homogeneous depth 4 arithmetic circuits. (English) Zbl 1359.68110 SIAM J. Comput. 46, No. 1, 336-387 (2017). MSC: 68Q17 12Y05 68Q05 68W30 PDFBibTeX XMLCite \textit{M. Kumar} and \textit{S. Saraf}, SIAM J. Comput. 46, No. 1, 336--387 (2017; Zbl 1359.68110) Full Text: DOI arXiv
Kayal, Neeraj; Limaye, Nutan; Saha, Chandan; Srinivasan, Srikanth An exponential lower bound for homogeneous depth four arithmetic formulas. (English) Zbl 1359.68108 SIAM J. Comput. 46, No. 1, 307-335 (2017). MSC: 68Q17 12Y05 68Q05 PDFBibTeX XMLCite \textit{N. Kayal} et al., SIAM J. Comput. 46, No. 1, 307--335 (2017; Zbl 1359.68108) Full Text: DOI
Cai, Jin-Yi; Chen, Xi; Lu, Pinyan Nonnegative weighted #CSP: an effective complexity dichotomy. (English) Zbl 1356.68094 SIAM J. Comput. 45, No. 6, 2177-2198 (2016). MSC: 68Q25 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., SIAM J. Comput. 45, No. 6, 2177--2198 (2016; Zbl 1356.68094) Full Text: DOI arXiv
Galanis, Andreas; Štefankovič, Daniel; Vigoda, Eric; Yang, Linji Ferromagnetic Potts model: refined \(\#\)BIS-hardness and related results. (English) Zbl 1355.68198 SIAM J. Comput. 45, No. 6, 2004-2065 (2016). MSC: 68Q87 05C80 68Q17 82C20 PDFBibTeX XMLCite \textit{A. Galanis} et al., SIAM J. Comput. 45, No. 6, 2004--2065 (2016; Zbl 1355.68198) Full Text: DOI Link
Cai, Jin-Yi; Guo, Heng; Williams, Tyson A complete dichotomy rises from the capture of vanishing signatures. (English) Zbl 1350.68133 SIAM J. Comput. 45, No. 5, 1671-1728 (2016). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., SIAM J. Comput. 45, No. 5, 1671--1728 (2016; Zbl 1350.68133) Full Text: DOI arXiv
Agrawal, Manindra; Saha, Chandan; Saptharishi, Ramprasad; Saxena, Nitin Jacobian hits circuits: hitting sets, lower bounds for depth-\(D\) occur-\(k\) formulas and depth-3 transcendence degree-\(k\) circuits. (English) Zbl 1350.68292 SIAM J. Comput. 45, No. 4, 1533-1562 (2016). MSC: 68W30 68Q05 68Q25 94C10 PDFBibTeX XMLCite \textit{M. Agrawal} et al., SIAM J. Comput. 45, No. 4, 1533--1562 (2016; Zbl 1350.68292) Full Text: DOI
Feldman, Vitaly; Vondrák, Jan Optimal bounds on approximation of submodular and XOS functions by juntas. (English) Zbl 1345.68251 SIAM J. Comput. 45, No. 3, 1129-1170 (2016). MSC: 68T05 PDFBibTeX XMLCite \textit{V. Feldman} and \textit{J. Vondrák}, SIAM J. Comput. 45, No. 3, 1129--1170 (2016; Zbl 1345.68251) Full Text: DOI arXiv
Gupta, Ankit; Kamath, Pritish; Kayal, Neeraj; Saptharishi, Ramprasad Arithmetic circuits: a chasm at depth 3. (English) Zbl 1344.68300 SIAM J. Comput. 45, No. 3, 1064-1079 (2016). MSC: 68W30 12E05 68Q05 68Q17 68W20 PDFBibTeX XMLCite \textit{A. Gupta} et al., SIAM J. Comput. 45, No. 3, 1064--1079 (2016; Zbl 1344.68300) Full Text: DOI
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark Approximately counting \(H\)-colorings is \(\#\)BIS-hard. (English) Zbl 1342.68147 SIAM J. Comput. 45, No. 3, 680-711 (2016). MSC: 68Q17 05C15 05C30 05C69 68W20 68W25 PDFBibTeX XMLCite \textit{A. Galanis} et al., SIAM J. Comput. 45, No. 3, 680--711 (2016; Zbl 1342.68147) Full Text: DOI
Feldman, Vitaly; Xiao, David Sample complexity bounds on differentially private learning via communication complexity. (English) Zbl 1331.68104 SIAM J. Comput. 44, No. 6, 1740-1764 (2015). MSC: 68Q25 68T05 94A60 94A62 PDFBibTeX XMLCite \textit{V. Feldman} and \textit{D. Xiao}, SIAM J. Comput. 44, No. 6, 1740--1764 (2015; Zbl 1331.68104) Full Text: DOI arXiv
Kumar, Mrinal; Saraf, Shubhangi The limits of depth reduction for arithmetic formulas: it’s all about the top fan-in. (English) Zbl 1330.68097 SIAM J. Comput. 44, No. 6, 1601-1625 (2015). MSC: 68Q17 68Q05 94C10 PDFBibTeX XMLCite \textit{M. Kumar} and \textit{S. Saraf}, SIAM J. Comput. 44, No. 6, 1601--1625 (2015; Zbl 1330.68097) Full Text: DOI arXiv
Fournier, Hervé; Limaye, Nutan; Malod, Guillaume; Srinivasan, Srikanth Lower bounds for depth-4 formulas computing iterated matrix multiplication. (English) Zbl 1330.68093 SIAM J. Comput. 44, No. 5, 1173-1201 (2015). MSC: 68Q17 68Q25 68W30 PDFBibTeX XMLCite \textit{H. Fournier} et al., SIAM J. Comput. 44, No. 5, 1173--1201 (2015; Zbl 1330.68093) Full Text: DOI
Hrubeš, Pavel; Tzameret, Iddo Short proofs for the determinant identities. (English) Zbl 1528.03238 SIAM J. Comput. 44, No. 2, 340-383 (2015). MSC: 03F20 03B05 03D15 68Q15 68Q17 68W30 PDFBibTeX XMLCite \textit{P. Hrubeš} and \textit{I. Tzameret}, SIAM J. Comput. 44, No. 2, 340--383 (2015; Zbl 1528.03238) Full Text: DOI arXiv
Gibbons, Phillip B.; Matias, Yossi; Ramachandran, Vijaya The queue-read queue-write PRAM model: Accounting for contention in parallel algorithms. (English) Zbl 0914.68069 SIAM J. Comput. 28, No. 2, 733-769 (1998). MSC: 68Q05 68Q25 68W15 PDFBibTeX XMLCite \textit{P. B. Gibbons} et al., SIAM J. Comput. 28, No. 2, 733--769 (1998; Zbl 0914.68069) Full Text: DOI