Hirahara, Shuichi Non-black-Box worst-case to average-case reductions within \(\mathsf{NP}\). (English) Zbl 07782637 SIAM J. Comput. 52, No. 6, FOCS18-349-FOCS18-382 (2023). MSC: 68Q15 68Q17 68Q30 94A60 PDFBibTeX XMLCite \textit{S. Hirahara}, SIAM J. Comput. 52, No. 6, FOCS18--349-FOCS18--382 (2023; Zbl 07782637) Full Text: DOI
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
Sherstov, Alexander A.; Storozhenko, Andrey A.; Wu, Pei An optimal separation of randomized and quantum query complexity. (English) Zbl 07680600 SIAM J. Comput. 52, No. 2, 525-567 (2023). MSC: 68Q12 68Q17 68Q15 81P45 PDFBibTeX XMLCite \textit{A. A. Sherstov} et al., SIAM J. Comput. 52, No. 2, 525--567 (2023; Zbl 07680600) Full Text: DOI arXiv
Chiesa, Alessandro; Gur, Tom; Shinkar, Igor Relaxed locally correctable codes with nearly-linear block length and constant query complexity. (English) Zbl 1512.68088 SIAM J. Comput. 51, No. 6, 1839-1865 (2022). MSC: 68P30 68Q17 68Q87 PDFBibTeX XMLCite \textit{A. Chiesa} et al., SIAM J. Comput. 51, No. 6, 1839--1865 (2022; Zbl 1512.68088) Full Text: DOI
Chattopadhyay, Arkadev; Mande, Nikhil S. A short list of equalities induces large sign-rank. (English) Zbl 1502.68124 SIAM J. Comput. 51, No. 3, 820-848 (2022). MSC: 68Q11 68Q06 68Q15 68Q17 PDFBibTeX XMLCite \textit{A. Chattopadhyay} and \textit{N. S. Mande}, SIAM J. Comput. 51, No. 3, 820--848 (2022; Zbl 1502.68124) Full Text: DOI
Bavarian, Mohammad; Vidick, Thomas; Yuen, Henry Anchored parallel repetition for nonlocal games. (English) Zbl 1483.68136 SIAM J. Comput. 51, No. 2, 214-253 (2022). MSC: 68Q12 68Q17 81P45 81P68 91A05 PDFBibTeX XMLCite \textit{M. Bavarian} et al., SIAM J. Comput. 51, No. 2, 214--253 (2022; Zbl 1483.68136) Full Text: DOI arXiv
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
Göös, Mika; Rubinstein, Aviad Near-optimal communication lower bounds for approximate Nash equilibria. (English) Zbl 07453415 SIAM J. Comput. 50, No. 5, FOCS18-316-FOCS18-348 (2021). MSC: 68Q11 91A05 91A10 91A68 PDFBibTeX XMLCite \textit{M. Göös} and \textit{A. Rubinstein}, SIAM J. Comput. 50, No. 5, FOCS18--316-FOCS18--348 (2021; Zbl 07453415) Full Text: DOI arXiv
Farhadi, Alireza; Hajiaghayi, MohammadTaghi; Larsen, Kasper Green; Shi, Elaine Lower bounds for external memory integer sorting via network coding. (English) Zbl 1475.94052 SIAM J. Comput. 50, No. 5, STOC19-87-STOC19-111 (2021). MSC: 94A24 68P10 68P20 PDFBibTeX XMLCite \textit{A. Farhadi} et al., SIAM J. Comput. 50, No. 5, STOC19--87-STOC19--111 (2021; Zbl 1475.94052) Full Text: DOI
Bausch, Johannes; Leditzky, Felix Error thresholds for arbitrary Pauli noise. (English) Zbl 1473.81049 SIAM J. Comput. 50, No. 4, 1410-1460 (2021). Reviewer: Haozhen Situ (Guangzhou) MSC: 81P45 81P47 81P73 05E18 81P40 60H40 81P68 81P70 94B70 PDFBibTeX XMLCite \textit{J. Bausch} and \textit{F. Leditzky}, SIAM J. Comput. 50, No. 4, 1410--1460 (2021; Zbl 1473.81049) Full Text: DOI arXiv
Lovett, Shachar Sparse MDS matrices over small fields: a proof of the GM-MDS conjecture. (English) Zbl 1495.11130 SIAM J. Comput. 50, No. 4, 1248-1262 (2021). MSC: 11T06 11T71 68P30 94B05 PDFBibTeX XMLCite \textit{S. Lovett}, SIAM J. Comput. 50, No. 4, 1248--1262 (2021; Zbl 1495.11130) Full Text: DOI
Dughmi, Shaddin; Xu, Haifeng Algorithmic Bayesian persuasion. (English) Zbl 1464.91022 SIAM J. Comput. 50, No. 3, STOC16-68-STOC16-97 (2021). MSC: 91A28 91A05 91A68 68Q17 91B44 PDFBibTeX XMLCite \textit{S. Dughmi} and \textit{H. Xu}, SIAM J. Comput. 50, No. 3, STOC16--68-STOC16--97 (2021; Zbl 1464.91022) Full Text: DOI arXiv
Ganor, Anat; Kol, Gillat; Raz, Ran Exponential separation of communication and external information. (English) Zbl 1464.68101 SIAM J. Comput. 50, No. 3, STOC16-236-STOC16-254 (2021). MSC: 68P30 68Q11 PDFBibTeX XMLCite \textit{A. Ganor} et al., SIAM J. Comput. 50, No. 3, STOC16--236-STOC16--254 (2021; Zbl 1464.68101) Full Text: DOI
Cohen, Gil Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. (English) Zbl 1467.05168 SIAM J. Comput. 50, No. 3, STOC16-30-STOC16-67 (2021). MSC: 05C55 05D10 94A17 PDFBibTeX XMLCite \textit{G. Cohen}, SIAM J. Comput. 50, No. 3, STOC16--30-STOC16--67 (2021; Zbl 1467.05168) Full Text: DOI
Applebaum, Benny; Arkis, Barak; Raykov, Pavel; Vasudevan, Prashant Nalini Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations. (English) Zbl 1459.94156 SIAM J. Comput. 50, No. 1, 32-67 (2021). MSC: 94A62 94A60 94A15 68P20 PDFBibTeX XMLCite \textit{B. Applebaum} et al., SIAM J. Comput. 50, No. 1, 32--67 (2021; Zbl 1459.94156) Full Text: DOI
Vidick, Thomas Erratum to: “Three-player entangled XOR games are NP-hard to approximate”. (English) Zbl 1470.81023 SIAM J. Comput. 49, No. 6, 1423-1427 (2020). MSC: 81P45 81P68 68Q10 91A06 81P40 81P15 68W25 PDFBibTeX XMLCite \textit{T. Vidick}, SIAM J. Comput. 49, No. 6, 1423--1427 (2020; Zbl 1470.81023) Full Text: DOI
Mahadev, Urmila Classical homomorphic encryption for quantum circuits. (English) Zbl 1457.81026 SIAM J. Comput. 49, No. 6, FOCS18-189-FOCS18-215 (2020). Reviewer: Carlos Pedro Gonçalves (Lisboa) MSC: 81P68 68Q12 81P94 81P45 94A60 PDFBibTeX XMLCite \textit{U. Mahadev}, SIAM J. Comput. 49, No. 6, FOCS18--189-FOCS18--215 (2020; Zbl 1457.81026) 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
Dvir, Zeev; Gopi, Sivakanth; Gu, Yuzhou; Wigderson, Avi Spanoids – an abstraction of spanning structures, and a barrier for LCCs. (English) Zbl 1443.68115 SIAM J. Comput. 49, No. 3, 465-496 (2020). MSC: 68R05 68P30 94B60 PDFBibTeX XMLCite \textit{Z. Dvir} et al., SIAM J. Comput. 49, No. 3, 465--496 (2020; Zbl 1443.68115) Full Text: DOI arXiv
Chee, Yeow Meng; Dao, Duc Tu; Kiah, Han Mao; Ling, San; Wei, Hengjia Robust positioning patterns with low redundancy. (English) Zbl 1432.68137 SIAM J. Comput. 49, No. 2, 284-317 (2020). MSC: 68P30 68U05 PDFBibTeX XMLCite \textit{Y. M. Chee} et al., SIAM J. Comput. 49, No. 2, 284--317 (2020; Zbl 1432.68137) Full Text: DOI arXiv
Farruggia, Andrea; Ferragina, Paolo; Frangioni, Antonio; Venturini, Rossano Bicriteria data compression. (English) Zbl 1493.68136 SIAM J. Comput. 48, No. 5, 1603-1642 (2019). MSC: 68P30 68W25 90C27 PDFBibTeX XMLCite \textit{A. Farruggia} et al., SIAM J. Comput. 48, No. 5, 1603--1642 (2019; Zbl 1493.68136) Full Text: DOI
Kane, Daniel; Lovett, Shachar; Rao, Sankeerth The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes. (English) Zbl 1419.05217 SIAM J. Comput. 48, No. 4, 1425-1435 (2019). MSC: 05E10 68P30 05C69 05C78 94B99 20C30 PDFBibTeX XMLCite \textit{D. Kane} et al., SIAM J. Comput. 48, No. 4, 1425--1435 (2019; Zbl 1419.05217) Full Text: DOI arXiv
Brassard, Gilles; Nayak, Ashwin; Tapp, Alain; Touchette, Dave; Unger, Falk Noisy interactive quantum communication. (English) Zbl 1427.81014 SIAM J. Comput. 48, No. 4, 1147-1195 (2019). Reviewer: Alexander Yurevich Vlasov (Sankt-Peterburg) MSC: 81P45 68Q12 81P70 94A24 81P40 94A40 PDFBibTeX XMLCite \textit{G. Brassard} et al., SIAM J. Comput. 48, No. 4, 1147--1195 (2019; Zbl 1427.81014) Full Text: DOI arXiv
Sherstov, Alexander A. The power of asymmetry in constant-depth circuits. (English) Zbl 1427.68079 SIAM J. Comput. 47, No. 6, 2362-2434 (2018). MSC: 68Q06 68Q11 68Q32 PDFBibTeX XMLCite \textit{A. A. Sherstov}, SIAM J. Comput. 47, No. 6, 2362--2434 (2018; Zbl 1427.68079) Full Text: DOI
Braverman, Mark; Garg, Ankit; Ko, Young Kun; Mao, Jieming; Touchette, Dave Near-optimal bounds on the bounded-round quantum communication complexity of disjointness. (English) Zbl 1408.68062 SIAM J. Comput. 47, No. 6, 2277-2314 (2018). Reviewer: Alexander Yurevich Vlasov (Sankt-Peterburg) MSC: 68Q12 81P68 PDFBibTeX XMLCite \textit{M. Braverman} et al., SIAM J. Comput. 47, No. 6, 2277--2314 (2018; Zbl 1408.68062) Full Text: DOI arXiv
Allender, Eric; Grochow, Joshua A.; van Melkebeek, Dieter; Moore, Cristopher; Morgan, Andrew Minimum circuit size, graph isomorphism, and related problems. (English) Zbl 1397.68082 SIAM J. Comput. 47, No. 4, 1339-1372 (2018). MSC: 68Q15 05C60 68Q17 68Q30 PDFBibTeX XMLCite \textit{E. Allender} et al., SIAM J. Comput. 47, No. 4, 1339--1372 (2018; Zbl 1397.68082) 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
Sherstov, Alexander A. Compressing interactive communication under product distributions. (English) Zbl 1391.68033 SIAM J. Comput. 47, No. 2, 367-419 (2018). MSC: 68P30 PDFBibTeX XMLCite \textit{A. A. Sherstov}, SIAM J. Comput. 47, No. 2, 367--419 (2018; Zbl 1391.68033) Full Text: DOI
Hatami, Hamed; Hosseini, Kaave; Lovett, Shachar Structure of protocols for XOR functions. (English) Zbl 1386.68062 SIAM J. Comput. 47, No. 1, 208-217 (2018). MSC: 68Q10 94A17 94C10 PDFBibTeX XMLCite \textit{H. Hatami} et al., SIAM J. Comput. 47, No. 1, 208--217 (2018; Zbl 1386.68062) Full Text: DOI
Bürgisser, Peter; Christandl, Matthias; Mulmuley, Ketan D.; Walter, Michael Membership in moment polytopes is in NP and coNP. (English) Zbl 1371.68105 SIAM J. Comput. 46, No. 3, 972-991 (2017). MSC: 68Q25 17B10 52B55 53D20 81R05 PDFBibTeX XMLCite \textit{P. Bürgisser} et al., SIAM J. Comput. 46, No. 3, 972--991 (2017; Zbl 1371.68105) Full Text: DOI arXiv
Beigi, Salman; Etesami, Omid; Gohari, Amin Deterministic randomness extraction from generalized and distributed Santha-Vazirani sources. (English) Zbl 1394.68147 SIAM J. Comput. 46, No. 1, 1-36 (2017). MSC: 68Q10 60C05 68Q30 68Q87 68W20 PDFBibTeX XMLCite \textit{S. Beigi} et al., SIAM J. Comput. 46, No. 1, 1--36 (2017; Zbl 1394.68147) Full Text: DOI
Chattopadhyay, Arkadev; Edmonds, Jeff; Ellen, Faith; Pitassi, Toniann Upper and lower bounds on the power of advice. (English) Zbl 1344.68089 SIAM J. Comput. 45, No. 4, 1412-1432 (2016). MSC: 68Q17 68Q25 68P05 68P30 PDFBibTeX XMLCite \textit{A. Chattopadhyay} et al., SIAM J. Comput. 45, No. 4, 1412--1432 (2016; Zbl 1344.68089) Full Text: DOI
Cohen, Gil Local correlation breakers and applications to three-source extractors and mergers. (English) Zbl 1348.68171 SIAM J. Comput. 45, No. 4, 1297-1338 (2016). MSC: 68Q87 68P30 PDFBibTeX XMLCite \textit{G. Cohen}, SIAM J. Comput. 45, No. 4, 1297--1338 (2016; Zbl 1348.68171) Full Text: DOI
Vidick, Thomas Three-player entangled XOR games are NP-hard to approximate. (English) Zbl 1342.81080 SIAM J. Comput. 45, No. 3, 1007-1063 (2016); erratum ibid. 49, No. 6, 1423-1427 (2020). MSC: 81P45 81P68 68Q10 91A06 81P40 81P15 68W25 PDFBibTeX XMLCite \textit{T. Vidick}, SIAM J. Comput. 45, No. 3, 1007--1063 (2016; Zbl 1342.81080) Full Text: DOI arXiv Link
Braverman, Mark Interactive information complexity. (English) Zbl 1330.68067 SIAM J. Comput. 44, No. 6, 1698-1739 (2015). MSC: 68Q05 68Q10 94A17 94A29 PDFBibTeX XMLCite \textit{M. Braverman}, SIAM J. Comput. 44, No. 6, 1698--1739 (2015; Zbl 1330.68067) Full Text: DOI
Ben-Sasson, Eli; Ron-Zewi, Noga From affine to two-source extractors via approximate duality. (English) Zbl 1330.68219 SIAM J. Comput. 44, No. 6, 1670-1697 (2015). MSC: 68Q87 05C55 05D10 60C05 68W20 94A17 PDFBibTeX XMLCite \textit{E. Ben-Sasson} and \textit{N. Ron-Zewi}, SIAM J. Comput. 44, No. 6, 1670--1697 (2015; Zbl 1330.68219) Full Text: DOI
Kerenidis, Iordanis; Laplante, Sophie; Lerays, Virginie; Roland, Jérémie; Xiao, David Lower bounds on information complexity via zero-communication protocols and applications. (English) Zbl 1330.68096 SIAM J. Comput. 44, No. 5, 1550-1572 (2015). MSC: 68Q17 68P30 68Q05 PDFBibTeX XMLCite \textit{I. Kerenidis} et al., SIAM J. Comput. 44, No. 5, 1550--1572 (2015; Zbl 1330.68096) Full Text: DOI arXiv Link
Aharonov, Dorit; Eldar, Lior Quantum locally testable codes. (English) Zbl 1326.81054 SIAM J. Comput. 44, No. 5, 1230-1262 (2015). MSC: 81P70 81P40 81P45 81P68 94B60 94B70 PDFBibTeX XMLCite \textit{D. Aharonov} and \textit{L. Eldar}, SIAM J. Comput. 44, No. 5, 1230--1262 (2015; Zbl 1326.81054) Full Text: DOI arXiv
De Marco, Gianluca; Kowalski, Dariusz R. Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel. (English) Zbl 1326.68329 SIAM J. Comput. 44, No. 3, 868-888 (2015). MSC: 68W15 68W40 94A40 PDFBibTeX XMLCite \textit{G. De Marco} and \textit{D. R. Kowalski}, SIAM J. Comput. 44, No. 3, 868--888 (2015; Zbl 1326.68329) Full Text: DOI
Bille, Philip; Landau, Gad M.; Raman, Rajeev; Sadakane, Kunihiko; Satti, Srinivasa Rao; Weimann, Oren Random access to grammar-compressed strings and trees. (English) Zbl 1329.68084 SIAM J. Comput. 44, No. 3, 513-539 (2015). MSC: 68P05 68P30 68Q42 68W32 PDFBibTeX XMLCite \textit{P. Bille} et al., SIAM J. Comput. 44, No. 3, 513--539 (2015; Zbl 1329.68084) Full Text: DOI Link
Aaronson, Scott; Drucker, Andrew A full characterization of quantum advice. (English) Zbl 1304.81059 SIAM J. Comput. 43, No. 3, 1131-1183 (2014). Reviewer: Eugene Kryachko (Liège) MSC: 81P68 81P10 94A15 94C10 68T05 PDFBibTeX XMLCite \textit{S. Aaronson} and \textit{A. Drucker}, SIAM J. Comput. 43, No. 3, 1131--1183 (2014; Zbl 1304.81059) Full Text: DOI Link
Ben-Sasson, Eli (ed.); Ostrovsky, Rafail (ed.) Special section on the fifty-second IEEE annual symposium on foundations of computer science (FOCS 2011). (English) Zbl 1298.00224 SIAM J. Comput. 43, No. 2, 654-654 (2014). MSC: 00B25 68-06 91-06 94-06 PDFBibTeX XMLCite \textit{E. Ben-Sasson} (ed.) and \textit{R. Ostrovsky} (ed.), SIAM J. Comput. 43, No. 2, 654--654 (2014; Zbl 1298.00224) Full Text: DOI
Lu, Hsueh-I Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits. (English) Zbl 1295.05089 SIAM J. Comput. 43, No. 2, 477-496 (2014). MSC: 05C10 05C85 68P05 68P30 68R10 PDFBibTeX XMLCite \textit{H.-I Lu}, SIAM J. Comput. 43, No. 2, 477--496 (2014; Zbl 1295.05089) Full Text: DOI arXiv
Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya Restricted isometry of Fourier matrices and list decodability of random linear codes. (English) Zbl 1321.94122 SIAM J. Comput. 42, No. 5, 1888-1914 (2013). MSC: 94B05 94B35 60G15 94A20 94B65 PDFBibTeX XMLCite \textit{M. Cheraghchi} et al., SIAM J. Comput. 42, No. 5, 1888--1914 (2013; Zbl 1321.94122) Full Text: DOI arXiv Link
Ferragina, Paolo; Nitto, Igor; Venturini, Rossano On the bit-complexity of Lempel-Ziv compression. (English) Zbl 1276.68069 SIAM J. Comput. 42, No. 4, 1521-1541 (2013). MSC: 68P30 68R10 68Q25 68P05 90C39 PDFBibTeX XMLCite \textit{P. Ferragina} et al., SIAM J. Comput. 42, No. 4, 1521--1541 (2013; Zbl 1276.68069) Full Text: DOI arXiv Link
Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup How to compress interactive communication. (English) Zbl 1272.68138 SIAM J. Comput. 42, No. 3, 1327-1363 (2013). MSC: 68Q17 68P30 PDFBibTeX XMLCite \textit{B. Barak} et al., SIAM J. Comput. 42, No. 3, 1327--1363 (2013; Zbl 1272.68138) Full Text: DOI
Chen, Victor; Grigorescu, Elena; de Wolf, Ronald Error-correcting data structures. (English) Zbl 1267.68101 SIAM J. Comput. 42, No. 1, 84-111 (2013). MSC: 68P05 68P30 94B65 PDFBibTeX XMLCite \textit{V. Chen} et al., SIAM J. Comput. 42, No. 1, 84--111 (2013; Zbl 1267.68101) Full Text: DOI arXiv
Censor-Hillel, Keren; Shachnai, Hadas Fast information spreading in graphs with large weak conductance. (English) Zbl 1261.68091 SIAM J. Comput. 41, No. 6, 1451-1465 (2012). MSC: 68Q85 68W15 68W05 68R10 PDFBibTeX XMLCite \textit{K. Censor-Hillel} and \textit{H. Shachnai}, SIAM J. Comput. 41, No. 6, 1451--1465 (2012; Zbl 1261.68091) Full Text: DOI
Sherstov, Alexander A. Strong direct product theorems for quantum communication and query complexity. (English) Zbl 1263.68050 SIAM J. Comput. 41, No. 5, 1122-1165 (2012). MSC: 68Q17 68Q12 81P45 81P68 PDFBibTeX XMLCite \textit{A. A. Sherstov}, SIAM J. Comput. 41, No. 5, 1122--1165 (2012; Zbl 1263.68050) Full Text: DOI arXiv
De, Anindya; Portmann, Christopher; Vidick, Thomas; Renner, Renato Trevisan’s extractor in the presence of quantum side information. (English) Zbl 1279.68275 SIAM J. Comput. 41, No. 4, 915-940 (2012). MSC: 68Q87 81P45 68Q12 81P94 94A17 PDFBibTeX XMLCite \textit{A. De} et al., SIAM J. Comput. 41, No. 4, 915--940 (2012; Zbl 1279.68275) Full Text: DOI Link
Gilbert, Anna C.; Li, Yi; Porat, Ely; Strauss, Martin J. Approximate sparse recovery: optimizing time and measurements. (English) Zbl 1259.94024 SIAM J. Comput. 41, No. 2, 436-453 (2012). MSC: 94A12 68W25 68W20 68P30 94B35 PDFBibTeX XMLCite \textit{A. C. Gilbert} et al., SIAM J. Comput. 41, No. 2, 436--453 (2012; Zbl 1259.94024) Full Text: DOI arXiv
Valiant, Paul Testing symmetric properties of distributions. (English) Zbl 1233.62112 SIAM J. Comput. 40, No. 6, 1927-1968 (2011). MSC: 62G99 62E99 62E10 68W99 94A17 PDFBibTeX XMLCite \textit{P. Valiant}, SIAM J. Comput. 40, No. 6, 1927--1968 (2011; Zbl 1233.62112) Full Text: DOI Link
Dvir, Zeev; Gopalan, Parikshit; Yekhanin, Sergey Matching vector codes. (English) Zbl 1228.68026 SIAM J. Comput. 40, No. 4, 1154-1178 (2011). MSC: 68P30 94A24 05B30 PDFBibTeX XMLCite \textit{Z. Dvir} et al., SIAM J. Comput. 40, No. 4, 1154--1178 (2011; Zbl 1228.68026) Full Text: DOI
Frieze, Alan; Melsted, Páll; Mitzenmacher, Michael An analysis of random-walk cuckoo hashing. (English) Zbl 1222.68073 SIAM J. Comput. 40, No. 2, 291-308 (2011). MSC: 68P10 68P30 PDFBibTeX XMLCite \textit{A. Frieze} et al., SIAM J. Comput. 40, No. 2, 291--308 (2011; Zbl 1222.68073) Full Text: DOI
Kushilevitz, Eyal; Lindell, Yehuda; Rabin, Tal Information-theoretically secure protocols and security under composition. (English) Zbl 1202.94185 SIAM J. Comput. 39, No. 5, 2090-2112 (2010). Reviewer: Tiit Riismaa (Tallinn) MSC: 94A60 68Q17 68Q25 PDFBibTeX XMLCite \textit{E. Kushilevitz} et al., SIAM J. Comput. 39, No. 5, 2090--2112 (2010; Zbl 1202.94185) Full Text: DOI
Kaufman, Tali; Litsyn, Simon; Xie, Ning Breaking the \(\epsilon\)-soundness bound of the linearity test over GF(2). (English) Zbl 1202.68178 SIAM J. Comput. 39, No. 5, 1988-2003 (2010). MSC: 68P30 68Q17 94B25 PDFBibTeX XMLCite \textit{T. Kaufman} et al., SIAM J. Comput. 39, No. 5, 1988--2003 (2010; Zbl 1202.68178) Full Text: DOI
Impagliazzo, Russell; Jaiswal, Ragesh; Kabanets, Valentine; Wigderson, Avi Uniform direct product theorems: simplified, optimized, and derandomized. (English) Zbl 1206.68131 SIAM J. Comput. 39, No. 4, 1637-1665 (2009). MSC: 68Q15 68Q17 68Q25 68P30 68W20 PDFBibTeX XMLCite \textit{R. Impagliazzo} et al., SIAM J. Comput. 39, No. 4, 1637--1665 (2009; Zbl 1206.68131) Full Text: DOI
Impagliazzo, Russell; Jaiswal, Ragesh; Kabanets, Valentine Approximate list-decoding of direct product codes and uniform hardness amplification. (English) Zbl 1200.68142 SIAM J. Comput. 39, No. 2, 564-605 (2009). MSC: 68Q45 68Q15 68Q17 68Q25 68P30 PDFBibTeX XMLCite \textit{R. Impagliazzo} et al., SIAM J. Comput. 39, No. 2, 564--605 (2009; Zbl 1200.68142) Full Text: DOI
Meir, Or Combinatorial construction of locally testable codes. (English) Zbl 1202.68235 SIAM J. Comput. 39, No. 2, 491-544 (2009). MSC: 94B60 68P30 PDFBibTeX XMLCite \textit{O. Meir}, SIAM J. Comput. 39, No. 2, 491--544 (2009; Zbl 1202.68235) Full Text: DOI Link
Rao, Anup Extractors for a constant number of polynomially small min-entropy independent sources. (English) Zbl 1185.68453 SIAM J. Comput. 39, No. 1, 168-194 (2009). MSC: 68Q87 68R10 94A17 PDFBibTeX XMLCite \textit{A. Rao}, SIAM J. Comput. 39, No. 1, 168--194 (2009; Zbl 1185.68453) Full Text: DOI
Gavinsky, Dmitry; Kempe, Julia; Regev, Oded; de Wolf, Ronald Bounded-error quantum state identification and exponential separations in communication complexity. (English) Zbl 1197.81087 SIAM J. Comput. 39, No. 1, 1-24 (2009). Reviewer: Nicolae Constantinescu (Craiova) MSC: 81P68 81P45 94A13 94B60 68Q30 PDFBibTeX XMLCite \textit{D. Gavinsky} et al., SIAM J. Comput. 39, No. 1, 1--24 (2009; Zbl 1197.81087) Full Text: DOI arXiv
Hon, Wing-Kai; Sadakane, Kunihiko; Sung, Wing-Kin Breaking a time-and-space barrier in constructing full-text indices. (English) Zbl 1191.68225 SIAM J. Comput. 38, No. 6, 2162-2178 (2009). MSC: 68P10 68P05 68P30 68W40 PDFBibTeX XMLCite \textit{W.-K. Hon} et al., SIAM J. Comput. 38, No. 6, 2162--2178 (2009; Zbl 1191.68225) Full Text: DOI Link
Ben-Sasson, Eli; Sudan, Madhu Short PCPs with polylog query complexity. (English) Zbl 1172.68025 SIAM J. Comput. 38, No. 2, 551-607 (2008). MSC: 68Q17 68P30 94B60 PDFBibTeX XMLCite \textit{E. Ben-Sasson} and \textit{M. Sudan}, SIAM J. Comput. 38, No. 2, 551--607 (2009; Zbl 1172.68025) Full Text: DOI
Fagin, Ronald (ed.); Gupta, Anupam (ed.); Kumar, Ravi (ed.); O’Donnell, Ryan (ed.) Special issue: Selected papers based on the presentations at the 37th annual ACM symposium on theory of computing (STOC 2005), Baltimore, MD, USA, May 22–24, 2005. (English) Zbl 1200.05004 SIAM J. Comput. 38, No. 2, vii, 449-752 (2008). MSC: 05-06 68-06 65-06 90-06 94-06 00B25 PDFBibTeX XML
Gavinsky, Dmitry; Kempe, Julia; Kerenidis, Iordanis; Raz, Ran; de Wolf, Ronald Exponential separation for one-way quantum communication complexity, with applications to cryptography. (English) Zbl 1175.81038 SIAM J. Comput. 38, No. 5, 1695-1708 (2008). MSC: 81P45 81P94 81P15 94A05 94A60 68P30 68Q01 PDFBibTeX XMLCite \textit{D. Gavinsky} et al., SIAM J. Comput. 38, No. 5, 1695--1708 (2008; Zbl 1175.81038) Full Text: DOI arXiv
Lutz, Jack H.; Mayordomo, Elvira Dimensions of points in self-similar fractals. (English) Zbl 1187.68269 SIAM J. Comput. 38, No. 3, 1080-1112 (2008). MSC: 68Q30 68Q15 03D99 28A78 11K55 PDFBibTeX XMLCite \textit{J. H. Lutz} and \textit{E. Mayordomo}, SIAM J. Comput. 38, No. 3, 1080--1112 (2008; Zbl 1187.68269) Full Text: DOI Link
Bar-Yossef, Ziv; Jayram, T. S.; Kerenidis, Iordanis Exponential separation of quantum and classical one-way communication complexity. (English) Zbl 1165.68028 SIAM J. Comput. 38, No. 1, 366-384 (2008). MSC: 68P30 68Q15 68Q17 81P68 PDFBibTeX XMLCite \textit{Z. Bar-Yossef} et al., SIAM J. Comput. 38, No. 1, 366--384 (2008; Zbl 1165.68028) Full Text: DOI Link
Dodis, Yevgeniy; Ostrovsky, Rafail; Reyzin, Leonid; Smith, Adam Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. (English) Zbl 1165.94326 SIAM J. Comput. 38, No. 1, 97-139 (2008). MSC: 94A62 94A60 68P25 68P30 68Q99 94A17 94B35 94B99 PDFBibTeX XMLCite \textit{Y. Dodis} et al., SIAM J. Comput. 38, No. 1, 97--139 (2008; Zbl 1165.94326) Full Text: DOI arXiv
Laplante, Sophie; Magniez, Frédéric Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. (English) Zbl 1158.81319 SIAM J. Comput. 38, No. 1, 46-62 (2008). MSC: 81P68 68Q30 PDFBibTeX XMLCite \textit{S. Laplante} and \textit{F. Magniez}, SIAM J. Comput. 38, No. 1, 46--62 (2008; Zbl 1158.81319) Full Text: DOI arXiv
Aiello, William; Leighton, F. T. Hamming codes, hypercube embeddings, and fault tolerance. (English) Zbl 1144.68008 SIAM J. Comput. 37, No. 3, 783-803 (2007). MSC: 68M10 68M15 68P30 68R10 PDFBibTeX XMLCite \textit{W. Aiello} and \textit{F. T. Leighton}, SIAM J. Comput. 37, No. 3, 783--803 (2007; Zbl 1144.68008) Full Text: DOI
Athreya, Krishna B.; Hitchcock, John M.; Lutz, Jack H.; Mayordomo, Elvira Effective strong dimension in algorithmic information and computational complexity. (English) Zbl 1144.68029 SIAM J. Comput. 37, No. 3, 671-705 (2007). MSC: 68Q30 68Q15 03D45 28A80 11K55 PDFBibTeX XMLCite \textit{K. B. Athreya} et al., SIAM J. Comput. 37, No. 3, 671--705 (2007; Zbl 1144.68029) Full Text: DOI
Bradford, Phillip G.; Katehakis, Michael N. A probabilistic study on combinatorial expanders and hashing. (English) Zbl 1137.05324 SIAM J. Comput. 37, No. 1, 83-111 (2007). MSC: 05C90 68P05 68P20 60C05 PDFBibTeX XMLCite \textit{P. G. Bradford} and \textit{M. N. Katehakis}, SIAM J. Comput. 37, No. 1, 83--111 (2007; Zbl 1137.05324) Full Text: DOI
Soloveichik, David; Winfree, Erik Complexity of self-assembled shapes. (English) Zbl 1136.68029 SIAM J. Comput. 36, No. 6, 1544-1569 (2007). MSC: 68Q30 68Q05 52C20 52C45 PDFBibTeX XMLCite \textit{D. Soloveichik} and \textit{E. Winfree}, SIAM J. Comput. 36, No. 6, 1544--1569 (2007; Zbl 1136.68029) Full Text: DOI
Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil Robust PCPs of proximity, shorter PCPs, and applications to coding. (English) Zbl 1118.68071 SIAM J. Comput. 36, No. 4, 889-974 (2006). MSC: 68Q17 68P30 94B60 PDFBibTeX XMLCite \textit{E. Ben-Sasson} et al., SIAM J. Comput. 36, No. 4, 889--974 (2006; Zbl 1118.68071) Full Text: DOI
Beigel, Richard; Fortnow, Lance; Stephan, Frank Infinitely-often autoreducible sets. (English) Zbl 1149.03030 SIAM J. Comput. 36, No. 3, 595-608 (2006). MSC: 03D15 03D30 68Q15 68Q30 PDFBibTeX XMLCite \textit{R. Beigel} et al., SIAM J. Comput. 36, No. 3, 595--608 (2006; Zbl 1149.03030) Full Text: DOI
Allender, Eric; Buhrman, Harry; Koucký, Michal; van Melkebeek, Dieter; Ronneburger, Detlef Power from random strings. (English) Zbl 1106.68049 SIAM J. Comput. 35, No. 6, 1467-1493 (2006). Reviewer: Cristian S. Calude (Auckland) MSC: 68Q30 68Q15 68Q17 68Q10 03D15 PDFBibTeX XMLCite \textit{E. Allender} et al., SIAM J. Comput. 35, No. 6, 1467--1493 (2006; Zbl 1106.68049) Full Text: DOI
Kjos-Hanssen, Bjorn; Nies, André; Stephan, Frank Lowness for the class of Schnorr random reals. (English) Zbl 1095.68043 SIAM J. Comput. 35, No. 3, 647-657 (2006). MSC: 68Q30 03D25 03D28 PDFBibTeX XMLCite \textit{B. Kjos-Hanssen} et al., SIAM J. Comput. 35, No. 3, 647--657 (2006; Zbl 1095.68043) Full Text: DOI arXiv
Grossi, Roberto; Vitter, Jeffrey Scott Compressed suffix arrays and suffix trees with applications to text indexing and string matching. (English) Zbl 1092.68115 SIAM J. Comput. 35, No. 2, 378-407 (2005). MSC: 68W05 68Q25 68P05 68P10 68P30 PDFBibTeX XMLCite \textit{R. Grossi} and \textit{J. S. Vitter}, SIAM J. Comput. 35, No. 2, 378--407 (2005; Zbl 1092.68115) Full Text: DOI
Bender, Michael A.; Demaine, Erik D.; Farach-Colton, Martin Cache-oblivious B-trees. (English) Zbl 1092.68028 SIAM J. Comput. 35, No. 2, 341-358 (2005). MSC: 68P05 68P30 68P20 PDFBibTeX XMLCite \textit{M. A. Bender} et al., SIAM J. Comput. 35, No. 2, 341--358 (2005; Zbl 1092.68028) Full Text: DOI
Batu, Tugkan; Dasgupta, Sanjoy; Kumar, Ravi; Rubinfeld, Ronitt The complexity of approximating the entropy. (English) Zbl 1087.94012 SIAM J. Comput. 35, No. 1, 132-150 (2005). MSC: 94A17 94A20 68W25 62G99 PDFBibTeX XMLCite \textit{T. Batu} et al., SIAM J. Comput. 35, No. 1, 132--150 (2005; Zbl 1087.94012) Full Text: DOI
Aggarwal, Gagan; Cheng, Qi; Goldwasser, Michael H.; Kao, Ming-Yang; de Espanes, Pablo Moisset; Schweller, Robert T. Complexities for generalized models of self-assembly. (English) Zbl 1088.68067 SIAM J. Comput. 34, No. 6, 1493-1515 (2005). MSC: 68Q17 05B45 05B50 52C20 52C45 68Q25 68Q30 PDFBibTeX XMLCite \textit{G. Aggarwal} et al., SIAM J. Comput. 34, No. 6, 1493--1515 (2005; Zbl 1088.68067) Full Text: DOI
Siegel, Alan On universal classes of extremely random constant-time hash functions. (English) Zbl 1082.68129 SIAM J. Comput. 33, No. 3, 505-543 (2004). MSC: 68W40 68P20 68W10 68W20 68R10 PDFBibTeX XMLCite \textit{A. Siegel}, SIAM J. Comput. 33, No. 3, 505--543 (2004; Zbl 1082.68129) Full Text: DOI
Crochemore, Maxime; Landau, Gad M.; Ziv-Ukelson, Michal A subquadratic sequence alignment algorithm for unrestricted scoring matrices. (English) Zbl 1253.74047 SIAM J. Comput. 32, No. 6, 1654-1673 (2003). MSC: 68W32 90C39 68P30 PDFBibTeX XMLCite \textit{M. Crochemore} et al., SIAM J. Comput. 32, No. 6, 1654--1673 (2003; Zbl 1253.74047) Full Text: DOI
Ambainis, Andris; Schulman, Leonard J.; Ta-Shma, Amnon; Vazirani, Umesh; Wigderson, Avi The quantum communication complexity of sampling. (English) Zbl 1041.68002 SIAM J. Comput. 32, No. 6, 1570-1585 (2003). MSC: 68M10 68Q10 68R05 PDFBibTeX XMLCite \textit{A. Ambainis} et al., SIAM J. Comput. 32, No. 6, 1570--1585 (2003; Zbl 1041.68002) Full Text: DOI
Ebert, Todd; Merkle, Wolfgang; Vollmer, Heribert On the autoreducibility of random sequences. (English) Zbl 1032.03036 SIAM J. Comput. 32, No. 6, 1542-1569 (2003). MSC: 03D15 03D30 03D10 68P30 68Q30 91A60 PDFBibTeX XMLCite \textit{T. Ebert} et al., SIAM J. Comput. 32, No. 6, 1542--1569 (2003; Zbl 1032.03036) Full Text: DOI
Glier, Oliver Kolmogorov complexity and deterministic context-free languages. (English) Zbl 1053.68052 SIAM J. Comput. 32, No. 5, 1389-1394 (2003). MSC: 68Q30 68Q45 PDFBibTeX XMLCite \textit{O. Glier}, SIAM J. Comput. 32, No. 5, 1389--1394 (2003; Zbl 1053.68052) Full Text: DOI
Downey, Rod G.; Hirschfeldt, Denis R.; Nies, André Randomness, computability, and density. (English) Zbl 1052.68060 SIAM J. Comput. 31, No. 4, 1169-1183 (2002). MSC: 68Q30 03D30 03D80 PDFBibTeX XMLCite \textit{R. G. Downey} et al., SIAM J. Comput. 31, No. 4, 1169--1183 (2002; Zbl 1052.68060) Full Text: DOI
Buhrman, Harry; Fortnow, Lance; Laplante, Sophie Resource-bounded Kolmogorov complexity revisited. (English) Zbl 1017.68061 SIAM J. Comput. 31, No. 3, 887-905 (2002). MSC: 68Q30 68Q15 PDFBibTeX XMLCite \textit{H. Buhrman} et al., SIAM J. Comput. 31, No. 3, 887--905 (2002; Zbl 1017.68061) Full Text: DOI
Buhrman, Harry; Longpré, Luc Compressibility and resource bounded measure. (English) Zbl 1015.68082 SIAM J. Comput. 31, No. 3, 876-886 (2002). MSC: 68Q30 28A99 68Q15 PDFBibTeX XMLCite \textit{H. Buhrman} and \textit{L. Longpré}, SIAM J. Comput. 31, No. 3, 876--886 (2002; Zbl 1015.68082) Full Text: DOI
Merkle, Wolfgang The global power of additional queries to \(p\)-random oracles. (English) Zbl 0997.03039 SIAM J. Comput. 31, No. 2, 483-495 (2001). Reviewer: U.Schöning (Ulm) MSC: 03D30 68Q15 03D15 68Q30 PDFBibTeX XMLCite \textit{W. Merkle}, SIAM J. Comput. 31, No. 2, 483--495 (2001; Zbl 0997.03039) Full Text: DOI
Pagh, Rasmus Low redundancy in static dictionaries with constant query time. (English) Zbl 0994.68050 SIAM J. Comput. 31, No. 2, 353-363 (2001). MSC: 68P10 68P30 68P20 PDFBibTeX XMLCite \textit{R. Pagh}, SIAM J. Comput. 31, No. 2, 353--363 (2001; Zbl 0994.68050) Full Text: DOI
Kucera, Antonín; Slaman, T. Randomness and recursive enumerability. (English) Zbl 0992.68079 SIAM J. Comput. 31, No. 1, 199-211 (2001). MSC: 68Q30 03D15 PDFBibTeX XMLCite \textit{A. Kucera} and \textit{T. Slaman}, SIAM J. Comput. 31, No. 1, 199--211 (2001; Zbl 0992.68079) Full Text: DOI
Buhrman, Harry; Torenvliet, Leen Randomness is hard. (English) Zbl 0977.68046 SIAM J. Comput. 30, No. 5, 1485-1501 (2000). MSC: 68Q30 68Q15 68Q17 68Q19 03D15 68Q10 PDFBibTeX XMLCite \textit{H. Buhrman} and \textit{L. Torenvliet}, SIAM J. Comput. 30, No. 5, 1485--1501 (2000; Zbl 0977.68046) Full Text: DOI
He, Xin; Kao, Ming-Yang; Lu, Hsueh-I A fast general methodology for information-theoretically optimal encodings of graphs. (English) Zbl 0965.05090 SIAM J. Comput. 30, No. 3, 838-846 (2000). MSC: 05C85 68R10 05C78 05C10 05C30 94A15 PDFBibTeX XMLCite \textit{X. He} et al., SIAM J. Comput. 30, No. 3, 838--846 (2000; Zbl 0965.05090) Full Text: DOI
Etzioni, Oren; Hanks, Steve; Jiang, Tao; Madani, Omid Optimal information gathering on the internet with time and cost constraints. (English) Zbl 0949.68006 SIAM J. Comput. 29, No. 5, 1596-1620 (2000). MSC: 68M10 68W10 90B35 68Q25 PDFBibTeX XMLCite \textit{O. Etzioni} et al., SIAM J. Comput. 29, No. 5, 1596--1620 (2000; Zbl 0949.68006) Full Text: DOI
Sweedyk, Z. A \(2\frac{1}{2}\)-approximation algorithm for shortest superstring. (English) Zbl 1051.68060 SIAM J. Comput. 29, No. 3, 954-986 (2000). MSC: 68P30 68P10 68W05 PDFBibTeX XMLCite \textit{Z. Sweedyk}, SIAM J. Comput. 29, No. 3, 954--986 (2000; Zbl 1051.68060) Full Text: DOI
Decatur, Scott E.; Goldreich, Oded; Ron, Dana Computational sample complexity. (English) Zbl 0941.68108 SIAM J. Comput. 29, No. 3, 854-879 (2000). MSC: 68T05 68Q15 PDFBibTeX XMLCite \textit{S. E. Decatur} et al., SIAM J. Comput. 29, No. 3, 854--879 (2000; Zbl 0941.68108) Full Text: DOI
Levene, Mark; Loizou, George Navigation in hypertext is easy only sometimes. (English) Zbl 0941.68038 SIAM J. Comput. 29, No. 3, 728-760 (2000). MSC: 68P15 68P20 68Q15 PDFBibTeX XMLCite \textit{M. Levene} and \textit{G. Loizou}, SIAM J. Comput. 29, No. 3, 728--760 (2000; Zbl 0941.68038) Full Text: DOI
Buhrman, Harry; Li, Ming; Tromp, John; Vitányi, Paul Kolmogorov random graphs and the incompressibility method. (English) Zbl 0939.68054 SIAM J. Comput. 29, No. 2, 590-599 (1999). MSC: 68Q30 05C35 05C30 05C80 PDFBibTeX XMLCite \textit{H. Buhrman} et al., SIAM J. Comput. 29, No. 2, 590--599 (1999; Zbl 0939.68054) Full Text: DOI arXiv
Parker, D. Stott; Ram, Prasad The construction of Huffman codes is a submodular (”convex”) optimization problem over a lattice of binary trees. (English) Zbl 0967.94005 SIAM J. Comput. 28, No. 5, 1875-1905 (1999). MSC: 94A45 94A15 94A29 94A24 05C05 06A07 PDFBibTeX XMLCite \textit{D. S. Parker} and \textit{P. Ram}, SIAM J. Comput. 28, No. 5, 1875--1905 (1999; Zbl 0967.94005) Full Text: DOI