Briët, Jop; Regev, Oded; Saket, Rishi Tight hardness of the non-commutative Grothendieck problem. (English) Zbl 1387.68122 Theory Comput. 13, Paper No. 15, 24 p. (2017). MSC: 68Q17 15A60 32A70 68W25 90C22 PDFBibTeX XMLCite \textit{J. Briët} et al., Theory Comput. 13, Paper No. 15, 24 p. (2017; Zbl 1387.68122) Full Text: DOI arXiv
Lee, Chin Ho; Viola, Emanuele Some limitations of the sum of small-bias distributions. (English) Zbl 1387.68125 Theory Comput. 13, Paper No. 16, 23 p. (2017). MSC: 68Q17 65C10 68Q25 68Q87 PDFBibTeX XMLCite \textit{C. H. Lee} and \textit{E. Viola}, Theory Comput. 13, Paper No. 16, 23 p. (2017; Zbl 1387.68125) Full Text: DOI
Harris, David G.; Srinivasan, Aravind A constructive Lovász local lemma for permutations. (English) Zbl 1387.68293 Theory Comput. 13, Paper No. 17, 41 p. (2017). MSC: 68W20 05A05 05B15 05C15 05C65 05C70 60C05 PDFBibTeX XMLCite \textit{D. G. Harris} and \textit{A. Srinivasan}, Theory Comput. 13, Paper No. 17, 41 p. (2017; Zbl 1387.68293) Full Text: DOI
Grochow, Joshua A. Monotone projection lower bounds from extended formulation lower bounds. (English) Zbl 1383.68036 Theory Comput. 13, Paper No. 18, 15 p. (2017). MSC: 68Q17 90C05 15A15 05C70 PDFBibTeX XMLCite \textit{J. A. Grochow}, Theory Comput. 13, Paper No. 18, 15 p. (2017; Zbl 1383.68036) Full Text: DOI arXiv
Håstad, Johan; Huang, Sangxia; Manokaran, Rajsekar; O’Donnell, Ryan; Wright, John Improved NP-inapproximability for \(2\)-variable linear equations. (English) Zbl 1382.68092 Theory Comput. 13, Paper No. 19, 51 p. (2017). MSC: 68Q17 68T20 68W25 PDFBibTeX XMLCite \textit{J. Håstad} et al., Theory Comput. 13, Paper No. 19, 51 p. (2017; Zbl 1382.68092) Full Text: DOI
Shepherd, F. Bruce; Vetta, Adrian R. The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems. (English) Zbl 1387.68127 Theory Comput. 13, Paper No. 20, 25 p. (2017). MSC: 68Q17 68Q25 68W25 90B10 PDFBibTeX XMLCite \textit{F. B. Shepherd} and \textit{A. R. Vetta}, Theory Comput. 13, Paper No. 20, 25 p. (2017; Zbl 1387.68127) Full Text: DOI arXiv
Kim, John Y.; Kopparty, Swastik Decoding Reed-Muller codes over product sets. (English) Zbl 1420.94114 Theory Comput. 13, Paper No. 21, 38 p. (2017). MSC: 94B35 11T71 68W30 PDFBibTeX XMLCite \textit{J. Y. Kim} and \textit{S. Kopparty}, Theory Comput. 13, Paper No. 21, 38 p. (2017; Zbl 1420.94114) Full Text: DOI
Dvir, Zeev; Saraf, Shubhangi; Wigderson, Avi Superquadratic lower bound for 3-query locally correctable codes over the reals. (English) Zbl 1375.94176 Theory Comput. 13, Paper No. 11, 36 p. (2017). MSC: 94B65 52C35 PDFBibTeX XMLCite \textit{Z. Dvir} et al., Theory Comput. 13, Paper No. 11, 36 p. (2017; Zbl 1375.94176) Full Text: DOI
Steinke, Thomas; Vadhan, Salil; Wan, Andrew Pseudorandomness and Fourier-growth bounds for width-3 branching programs. (English) Zbl 1377.65003 Theory Comput. 13, Paper No. 12, 50 p. (2017). MSC: 65C10 68Q87 65T40 PDFBibTeX XMLCite \textit{T. Steinke} et al., Theory Comput. 13, Paper No. 12, 50 p. (2017; Zbl 1377.65003) Full Text: DOI arXiv
Balcan, Maria-Florina; Braverman, Mark Nash equilibria in perturbation-stable games. (English) Zbl 1380.91011 Theory Comput. 13, Paper No. 13, 31 p. (2017). MSC: 91A05 68Q17 68W25 91A10 PDFBibTeX XMLCite \textit{M.-F. Balcan} and \textit{M. Braverman}, Theory Comput. 13, Paper No. 13, 31 p. (2017; Zbl 1380.91011) Full Text: DOI arXiv
Felber, David; Ostrovsky, Rafail A randomized online quantile summary in \(O((1/\varepsilon) \log(1/\varepsilon))\) words. (English) Zbl 1382.68325 Theory Comput. 13, Paper No. 14, 17 p. (2017). MSC: 68W20 68P05 68W25 68W27 PDFBibTeX XMLCite \textit{D. Felber} and \textit{R. Ostrovsky}, Theory Comput. 13, Paper No. 14, 17 p. (2017; Zbl 1382.68325) Full Text: DOI
Harsha, Prahladh (ed.) Special issue: CCC 2016. Guest editor’s foreword. (English) Zbl 1372.00108 Theory Comput. 13, Paper No. 1, 3 p. (2017). MSC: 00B25 68-06 PDFBibTeX XMLCite \textit{P. Harsha} (ed.), Theory Comput. 13, Paper No. 1, 3 p. (2017; Zbl 1372.00108) Full Text: DOI
Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. (English) Zbl 1378.68080 Theory Comput. 13, Paper No. 2, 21 p. (2017). MSC: 68Q25 12Y05 68W30 PDFBibTeX XMLCite \textit{R. Gurjar} et al., Theory Comput. 13, Paper No. 2, 21 p. (2017; Zbl 1378.68080) Full Text: DOI arXiv
Guruswami, Venkatesan; Lee, Euiwoong Towards a characterization of approximation resistance for symmetric CSPs. (English) Zbl 1379.68282 Theory Comput. 13, Paper No. 3, 24 p. (2017). MSC: 68T20 68Q17 68Q25 68W25 90C22 PDFBibTeX XMLCite \textit{V. Guruswami} and \textit{E. Lee}, Theory Comput. 13, Paper No. 3, 24 p. (2017; Zbl 1379.68282) Full Text: DOI
Murray, Cody D.; Williams, R. Ryan On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity. (English) Zbl 1378.68053 Theory Comput. 13, Paper No. 4, 22 p. (2017). MSC: 68Q17 68Q15 94C10 PDFBibTeX XMLCite \textit{C. D. Murray} and \textit{R. R. Williams}, Theory Comput. 13, Paper No. 4, 22 p. (2017; Zbl 1378.68053) Full Text: DOI
Makarychev, Yury; Nayyeri, Amir; Sidiropoulos, Anastasios A pseudo-approximation for the genus of Hamiltonian graphs. (English) Zbl 1379.68356 Theory Comput. 13, Paper No. 5, 47 p. (2017). MSC: 68W25 05C10 05C45 05C85 68R10 PDFBibTeX XMLCite \textit{Y. Makarychev} et al., Theory Comput. 13, Paper No. 5, 47 p. (2017; Zbl 1379.68356) Full Text: DOI
Kumar, Mrinal; Saraf, Shubhangi Arithmetic circuits with locally low algebraic rank. (English) Zbl 1378.68051 Theory Comput. 13, Paper No. 6, 33 p. (2017). MSC: 68Q17 12Y05 68Q15 94C10 PDFBibTeX XMLCite \textit{M. Kumar} and \textit{S. Saraf}, Theory Comput. 13, Paper No. 6, 33 p. (2017; Zbl 1378.68051) Full Text: DOI arXiv
Gilmer, Justin; Koucký, Michal; Saks, Michael A communication game related to the sensitivity conjecture. (English) Zbl 1379.68151 Theory Comput. 13, Paper No. 7, 18 p. (2017). MSC: 68Q17 68Q25 91A80 94C10 PDFBibTeX XMLCite \textit{J. Gilmer} et al., Theory Comput. 13, Paper No. 7, 18 p. (2017; Zbl 1379.68151) Full Text: DOI
Coja-Oghlan, Amin; Cooley, Oliver; Kang, Mihyun; Skubch, Kathrin The minimum bisection in the planted bisection model. (English) Zbl 1379.05099 Theory Comput. 13, Paper No. 8, 22 p. (2017). MSC: 05C80 05C70 PDFBibTeX XMLCite \textit{A. Coja-Oghlan} et al., Theory Comput. 13, Paper No. 8, 22 p. (2017; Zbl 1379.05099) Full Text: DOI
Fournier, Hervé; Limaye, Nutan; Mahajan, Meena; Srinivasan, Srikanth The shifted partial derivative complexity of elementary symmetric polynomials. (English) Zbl 1379.68149 Theory Comput. 13, Paper No. 9, 34 p. (2017). MSC: 68Q17 68Q15 68Q25 PDFBibTeX XMLCite \textit{H. Fournier} et al., Theory Comput. 13, Paper No. 9, 34 p. (2017; Zbl 1379.68149) Full Text: DOI
Håstad, Johan; Manokaran, Rajsekar On the hardness of approximating balanced homogenous 3-Lin. (English) Zbl 1379.68154 Theory Comput. 13, Paper No. 10, 19 p. (2017). MSC: 68Q17 68Q15 68Q25 PDFBibTeX XMLCite \textit{J. Håstad} and \textit{R. Manokaran}, Theory Comput. 13, Paper No. 10, 19 p. (2017; Zbl 1379.68154) Full Text: DOI