Sherstov, Alexander A. On multiparty communication with large versus unbounded error. (English) Zbl 1412.68061 Theory Comput. 14, Paper No. 22, 17 p. (2018). MSC: 68Q05 68Q10 68Q15 68Q17 94C10 PDFBibTeX XMLCite \textit{A. A. Sherstov}, Theory Comput. 14, Paper No. 22, 17 p. (2018; Zbl 1412.68061) Full Text: DOI
Chattopadhyay, Arkadev; Mande, Nikhil S. Separation of unbounded-error models in multi-party communication complexity. (English) Zbl 1414.68027 Theory Comput. 14, Paper No. 21, 23 p. (2018). MSC: 68Q05 68Q10 68Q15 68Q17 94C10 PDFBibTeX XMLCite \textit{A. Chattopadhyay} and \textit{N. S. Mande}, Theory Comput. 14, Paper No. 21, 23 p. (2018; Zbl 1414.68027) Full Text: DOI
Rao, Anup; Sinha, Makrand Simplified separation of information and communication. (English) Zbl 1412.68060 Theory Comput. 14, Paper No. 20, 29 p. (2018). MSC: 68Q05 68Q10 68Q17 68Q85 68Q87 PDFBibTeX XMLCite \textit{A. Rao} and \textit{M. Sinha}, Theory Comput. 14, Paper No. 20, 29 p. (2018; Zbl 1412.68060) Full Text: DOI
Acharya, Jayadev; Canonne, Clément L.; Kamath, Gautam A chasm between identity and equivalence testing with conditional queries. (English) Zbl 1412.68293 Theory Comput. 14, Paper No. 19, 46 p. (2018). MSC: 68W20 60C05 60E15 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Acharya} et al., Theory Comput. 14, Paper No. 19, 46 p. (2018; Zbl 1412.68293) Full Text: DOI
Forbes, Michael A.; Shpilka, Amir; Volk, Ben Lee Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. (English) Zbl 1412.68081 Theory Comput. 14, Paper No. 18, 45 p. (2018). MSC: 68Q25 68Q17 68W20 PDFBibTeX XMLCite \textit{M. A. Forbes} et al., Theory Comput. 14, Paper No. 18, 45 p. (2018; Zbl 1412.68081) Full Text: DOI
Williams, R. Ryan New algorithms and lower bounds for circuits with linear threshold gates. (English) Zbl 1410.68127 Theory Comput. 14, Paper No. 17, 25 p. (2018). MSC: 68Q05 68Q17 68Q25 68W40 94C10 PDFBibTeX XMLCite \textit{R. R. Williams}, Theory Comput. 14, Paper No. 17, 25 p. (2018; Zbl 1410.68127) Full Text: DOI arXiv
Kayal, Neeraj; Saha, Chandan; Tavenas, Sébastien On the size of homogeneous and of depth-four formulas with low individual degree. (English) Zbl 1410.68125 Theory Comput. 14, Paper No. 16, 46 p. (2018). MSC: 68Q05 68Q17 PDFBibTeX XMLCite \textit{N. Kayal} et al., Theory Comput. 14, Paper No. 16, 46 p. (2018; Zbl 1410.68125) Full Text: DOI
Montanaro, Ashley Quantum-walk speedup of backtracking algorithms. (English) Zbl 1417.68046 Theory Comput. 14, Paper No. 15, 24 p. (2018). Reviewer: Alexander Yurevich Vlasov (Sankt-Peterburg) MSC: 68Q12 05C81 81P68 PDFBibTeX XMLCite \textit{A. Montanaro}, Theory Comput. 14, Paper No. 15, 24 p. (2018; Zbl 1417.68046) Full Text: DOI arXiv
Bazzi, Abbas; Fiorini, Samuel; Huang, Sangxia; Svensson, Ola Small extended formulation for knapsack cover inequalities from monotone circuits. (English) Zbl 1426.90211 Theory Comput. 14, Paper No. 14, 29 p. (2018). MSC: 90C27 90C59 68Q25 PDFBibTeX XMLCite \textit{A. Bazzi} et al., Theory Comput. 14, Paper No. 14, 29 p. (2018; Zbl 1426.90211) Full Text: DOI
Micciancio, Daniele On the hardness of learning with errors with binary secrets. (English) Zbl 1412.68072 Theory Comput. 14, Paper No. 13, 17 p. (2018). MSC: 68Q17 11H06 52C07 94A60 PDFBibTeX XMLCite \textit{D. Micciancio}, Theory Comput. 14, Paper No. 13, 17 p. (2018; Zbl 1412.68072) Full Text: DOI
Kopparty, Swastik; Srinivasan, Srikanth Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression. (English) Zbl 1412.68071 Theory Comput. 14, Paper No. 12, 24 p. (2018). MSC: 68Q17 68Q15 94C10 PDFBibTeX XMLCite \textit{S. Kopparty} and \textit{S. Srinivasan}, Theory Comput. 14, Paper No. 12, 24 p. (2018; Zbl 1412.68071) Full Text: DOI
Ben-David, Shalev; Kothari, Robin Randomized query complexity of sabotaged and composed functions. (English) Zbl 1398.68186 Theory Comput. 14, Paper No. 5, 27 p. (2018). MSC: 68Q17 68Q10 68W20 PDFBibTeX XMLCite \textit{S. Ben-David} and \textit{R. Kothari}, Theory Comput. 14, Paper No. 5, 27 p. (2018; Zbl 1398.68186) Full Text: DOI arXiv
Dagan, Yuval; Filmus, Yuval; Hatami, Hamed; Li, Yaqiao Trading information complexity for error. (English) Zbl 1394.68148 Theory Comput. 14, Paper No. 6, 73 p. (2018). MSC: 68Q10 68P30 PDFBibTeX XMLCite \textit{Y. Dagan} et al., Theory Comput. 14, Paper No. 6, 73 p. (2018; Zbl 1394.68148) Full Text: DOI
Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth Average-case lower bounds and satisfiability algorithms for small threshold circuits. (English) Zbl 1395.68138 Theory Comput. 14, Paper No. 9, 55 p. (2018). MSC: 68Q17 68Q05 68T20 94C10 PDFBibTeX XMLCite \textit{R. Chen} et al., Theory Comput. 14, Paper No. 9, 55 p. (2018; Zbl 1395.68138) Full Text: DOI
Dulek, Yfke; Schaffner, Christian; Speelman, Florian Quantum homomorphic encryption for polynomial-size circuits. (English) Zbl 1408.94933 Theory Comput. 14, Paper No. 7, 45 p. (2018). MSC: 94A60 81P68 81P94 PDFBibTeX XMLCite \textit{Y. Dulek} et al., Theory Comput. 14, Paper No. 7, 45 p. (2018; Zbl 1408.94933) Full Text: DOI arXiv
Broadbent, Anne How to verify a quantum computation. (English) Zbl 1395.68142 Theory Comput. 14, Paper No. 11, 37 p. (2018). MSC: 68Q25 68Q12 81P68 81P94 PDFBibTeX XMLCite \textit{A. Broadbent}, Theory Comput. 14, Paper No. 11, 37 p. (2018; Zbl 1395.68142) Full Text: DOI arXiv
Murtagh, Jack; Vadhan, Salil The complexity of computing the optimal composition of differential privacy. (English) Zbl 1395.94305 Theory Comput. 14, Paper No. 8, 35 p. (2018). MSC: 94A60 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{J. Murtagh} and \textit{S. Vadhan}, Theory Comput. 14, Paper No. 8, 35 p. (2018; Zbl 1395.94305) Full Text: DOI
Ghosh, Mrinalkanti; Tulsiani, Madhur From weak to strong linear programming gaps for all constraint satisfaction problems. (English) Zbl 1394.68178 Theory Comput. 14, Paper No. 10, 33 p. (2018). MSC: 68Q25 68Q17 90C05 90C10 90C22 90C25 PDFBibTeX XMLCite \textit{M. Ghosh} and \textit{M. Tulsiani}, Theory Comput. 14, Paper No. 10, 33 p. (2018; Zbl 1394.68178) Full Text: DOI
Applebaum, Benny; David, Liron; Even, Guy Explicit rateless codes for memoryless binary-input output-symmetric channels. (English) Zbl 1395.94229 Theory Comput. 14, Paper No. 4, 29 p. (2018). MSC: 94A24 94A40 94B05 PDFBibTeX XMLCite \textit{B. Applebaum} et al., Theory Comput. 14, Paper No. 4, 29 p. (2018; Zbl 1395.94229) Full Text: DOI
Arad, Itai; Santha, Miklos; Sundaram, Aarthi; Zhang, Shengyu Linear-time algorithm for quantum 2SAT. (English) Zbl 1395.68132 Theory Comput. 14, Paper No. 1, 27 p. (2018). MSC: 68Q12 PDFBibTeX XMLCite \textit{I. Arad} et al., Theory Comput. 14, Paper No. 1, 27 p. (2018; Zbl 1395.68132) Full Text: DOI
Bläser, Markus; Jindal, Gorav; Pandey, Anurag A deterministic PTAS for the commutative rank of matrix spaces. (English) Zbl 1395.68333 Theory Comput. 14, Paper No. 3, 21 p. (2018). MSC: 68W25 15A03 68Q25 PDFBibTeX XMLCite \textit{M. Bläser} et al., Theory Comput. 14, Paper No. 3, 21 p. (2018; Zbl 1395.68333) Full Text: DOI
Lovett, Shachar (ed.); O’Donnell, Ryan (ed.) Special issue: CCC 2017: guest editor’s foreword. (English) Zbl 1390.00162 Theory Comput. 14, Paper No. 2, 2 p. (2018). MSC: 00B25 68-06 68Q25 PDFBibTeX XMLCite \textit{S. Lovett} (ed.) and \textit{R. O'Donnell} (ed.), Theory Comput. 14, Paper No. 2, 2 p. (2018; Zbl 1390.00162) Full Text: DOI