Zhang, Shuangjun; Kan, Haibin; Wang, Liguan Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs. (English) Zbl 07570320 Theor. Comput. Sci. 927, 148-161 (2022). MSC: 68Qxx PDF BibTeX XML Cite \textit{S. Zhang} et al., Theor. Comput. Sci. 927, 148--161 (2022; Zbl 07570320) Full Text: DOI OpenURL
Chen, Lijie; Ren, Hanlin Strong average-case circuit lower bounds from nontrivial derandomization. (English) Zbl 07534654 SIAM J. Comput. 51, No. 3, STOC20-115-STOC20-173 (2022). MSC: 68Q05 68Q17 PDF BibTeX XML Cite \textit{L. Chen} and \textit{H. Ren}, SIAM J. Comput. 51, No. 3, STOC20--115-STOC20--173 (2022; Zbl 07534654) Full Text: DOI OpenURL
Bitansky, Nir; Chiesa, Alessandro; Ishai, Yuval; Ostrovsky, Rafail; Paneth, Omer Succinct non-interactive arguments via linear interactive proofs. (English) Zbl 1487.94103 J. Cryptology 35, No. 3, Paper No. 15, 72 p. (2022). MSC: 94A60 94A62 68Q25 PDF BibTeX XML Cite \textit{N. Bitansky} et al., J. Cryptology 35, No. 3, Paper No. 15, 72 p. (2022; Zbl 1487.94103) Full Text: DOI OpenURL
Stanković, Aleksa On regularity of Max-CSPs and Min-CSPs. (English) Zbl 1484.68332 Inf. Process. Lett. 176, Article ID 106244, 17 p. (2022). MSC: 68W25 68R07 PDF BibTeX XML Cite \textit{A. Stanković}, Inf. Process. Lett. 176, Article ID 106244, 17 p. (2022; Zbl 1484.68332) Full Text: DOI OpenURL
Mukhopadhyay, Priyanka The projection games conjecture and the hardness of approximation of Super-SAT and related problems. (English) Zbl 1472.68064 J. Comput. Syst. Sci. 123, 186-201 (2022). MSC: 68Q17 68R05 68R07 PDF BibTeX XML Cite \textit{P. Mukhopadhyay}, J. Comput. Syst. Sci. 123, 186--201 (2022; Zbl 1472.68064) Full Text: DOI arXiv OpenURL
Chiesa, Alessandro; Yogev, Eylon Subquadratic SNARGs in the random oracle model. (English) Zbl 1485.94073 Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12825, 711-741 (2021). MSC: 94A60 PDF BibTeX XML Cite \textit{A. Chiesa} and \textit{E. Yogev}, Lect. Notes Comput. Sci. 12825, 711--741 (2021; Zbl 1485.94073) Full Text: DOI OpenURL
Meer, Klaus A PCP of proximity for real algebraic polynomials. (English) Zbl 07493536 Santhanam, Rahul (ed.) et al., Computer science – theory and applications. 16th international computer science symposium in Russia, CSR 2021, Sochi, Russia, June 28 – July 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12730, 264-282 (2021). MSC: 68Qxx PDF BibTeX XML Cite \textit{K. Meer}, Lect. Notes Comput. Sci. 12730, 264--282 (2021; Zbl 07493536) Full Text: DOI OpenURL
Khachay, Michael; Ogorodnikov, Yuri; Khachay, Daniel Efficient approximation of the metric CVRP in spaces of fixed doubling dimension. (English) Zbl 1475.90082 J. Glob. Optim. 80, No. 3, 679-710 (2021). MSC: 90C27 90B06 90C59 PDF BibTeX XML Cite \textit{M. Khachay} et al., J. Glob. Optim. 80, No. 3, 679--710 (2021; Zbl 1475.90082) Full Text: DOI OpenURL
Paradise, Orr Smooth and strong PCPs. (English) Zbl 1485.68101 Comput. Complexity 30, No. 1, Paper No. 1, 77 p. (2021); corrigendum ibid. 30, No. 1, Paper No. 9, 1 p. (2021). Reviewer: Arne Meier (Hannover) MSC: 68Q15 68Q10 68Q17 68W20 PDF BibTeX XML Cite \textit{O. Paradise}, Comput. Complexity 30, No. 1, Paper No. 1, 77 p. (2021; Zbl 1485.68101) Full Text: DOI OpenURL
Briët, Jop; Labib, Farrokh High-entropy dual functions over finite fields and locally decodable codes. (English) Zbl 07319055 Forum Math. Sigma 9, Paper No. e19, 10 p. (2021). MSC: 11B30 11B25 PDF BibTeX XML Cite \textit{J. Briët} and \textit{F. Labib}, Forum Math. Sigma 9, Paper No. e19, 10 p. (2021; Zbl 07319055) Full Text: DOI arXiv OpenURL
van Ee, Martijn; Sitters, René The Chinese deliveryman problem. (English) Zbl 1468.90116 4OR 18, No. 3, 341-356 (2020). MSC: 90C27 68Q17 90C59 PDF BibTeX XML Cite \textit{M. van Ee} and \textit{R. Sitters}, 4OR 18, No. 3, 341--356 (2020; Zbl 1468.90116) Full Text: DOI OpenURL
Chuzhoy, Julia; Kim, David H. K.; Nimavat, Rachit New hardness results for routing on disjoint paths. (English) Zbl 07294218 SIAM J. Comput. 49, No. 6, STOC17-189-STOC17-237 (2020). MSC: 68Q25 68W25 PDF BibTeX XML Cite \textit{J. Chuzhoy} et al., SIAM J. Comput. 49, No. 6, STOC17--189-STOC17--237 (2020; Zbl 07294218) Full Text: DOI arXiv OpenURL
Chalermsook, Parinya; Cygan, Marek; Kortsarz, Guy; Laekhanukit, Bundit; Manurangsi, Pasin; Nanongkai, Danupon; Trevisan, Luca From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more. (English) Zbl 1452.68083 SIAM J. Comput. 49, No. 4, 772-810 (2020). MSC: 68Q17 05C69 68Q27 68R10 68W25 68W40 PDF BibTeX XML Cite \textit{P. Chalermsook} et al., SIAM J. Comput. 49, No. 4, 772--810 (2020; Zbl 1452.68083) Full Text: DOI OpenURL
Ertem, Zeynep; Lykhovyd, Eugene; Wang, Yiming; Butenko, Sergiy The maximum independent union of cliques problem: complexity and exact approaches. (English) Zbl 1448.90093 J. Glob. Optim. 76, No. 3, 545-562 (2020). Reviewer: Patric R. J. Östergård (Aalto) MSC: 90C35 68Q25 90C10 90C57 PDF BibTeX XML Cite \textit{Z. Ertem} et al., J. Glob. Optim. 76, No. 3, 545--562 (2020; Zbl 1448.90093) Full Text: DOI OpenURL
Coudron, Matthew; Slofstra, William Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision. (English) Zbl 07564425 Shpilka, Amir (ed.), 34th computational complexity conference, CCC 2019, New Brunswick, NJ, USA, July 18–20, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 137, Article 25, 20 p. (2019). MSC: 68Q25 PDF BibTeX XML Cite \textit{M. Coudron} and \textit{W. Slofstra}, LIPIcs -- Leibniz Int. Proc. Inform. 137, Article 25, 20 p. (2019; Zbl 07564425) Full Text: DOI OpenURL
Grilo, Alex B. A simple protocol for verifiable delegation of quantum computation in one round. (English) Zbl 07561521 Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 28, 13 p. (2019). MSC: 68Nxx 68Qxx PDF BibTeX XML Cite \textit{A. B. Grilo}, LIPIcs -- Leibniz Int. Proc. Inform. 132, Article 28, 13 p. (2019; Zbl 07561521) Full Text: DOI OpenURL
Dinur, Irit; Goldreich, Oded; Gur, Tom Every set in \(\mathcal{P}\) is strongly testable under a suitable encoding. (English) Zbl 07559073 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 30, 17 p. (2019). MSC: 68Qxx PDF BibTeX XML Cite \textit{I. Dinur} et al., LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 30, 17 p. (2019; Zbl 07559073) Full Text: DOI OpenURL
Chiesa, Alessandro; Manohar, Peter; Shinkar, Igor Probabilistic checking against non-signaling strategies from linearity testing. (English) Zbl 07559068 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 25, 17 p. (2019). MSC: 68Qxx PDF BibTeX XML Cite \textit{A. Chiesa} et al., LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 25, 17 p. (2019; Zbl 07559068) Full Text: DOI OpenURL
Stern, Roni; Dreiman, Gal; Valenzano, Richard Probably bounded suboptimal heuristic search. (English) Zbl 1478.68337 Artif. Intell. 267, 39-57 (2019). MSC: 68T20 PDF BibTeX XML Cite \textit{R. Stern} et al., Artif. Intell. 267, 39--57 (2019; Zbl 1478.68337) Full Text: DOI OpenURL
Kiyoshima, Susumu Non-black-box simulation in the fully concurrent setting, revisited. (English) Zbl 1434.94072 J. Cryptology 32, No. 2, 393-434 (2019). MSC: 94A60 PDF BibTeX XML Cite \textit{S. Kiyoshima}, J. Cryptology 32, No. 2, 393--434 (2019; Zbl 1434.94072) Full Text: DOI OpenURL
Chen, Yijia; Lin, Bingkai The constant inapproximability of the parameterized dominating set problem. (English) Zbl 1422.68082 SIAM J. Comput. 48, No. 2, 513-533 (2019). MSC: 68Q17 05C69 68Q25 68R10 PDF BibTeX XML Cite \textit{Y. Chen} and \textit{B. Lin}, SIAM J. Comput. 48, No. 2, 513--533 (2019; Zbl 1422.68082) Full Text: DOI arXiv OpenURL
Viderman, Michael Explicit strong LTCs with inverse poly-log rate and constant soundness. (English) Zbl 07378670 Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 58, 14 p. (2018). MSC: 68W20 68W25 90C27 PDF BibTeX XML Cite \textit{M. Viderman}, LIPIcs -- Leibniz Int. Proc. Inform. 116, Article 58, 14 p. (2018; Zbl 07378670) Full Text: DOI OpenURL
Manurangsi, Pasin; Trevisan, Luca Mildly exponential time approximation algorithms for vertex cover, balanced separator and uniform sparsest cut. (English) Zbl 07378632 Blais, Eric (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 21st international workshop, APPROX 2018, and 22nd international workshop, RANDOM 2018 August 20–22, 2018, Princeton, USA. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 116, Article 20, 17 p. (2018). MSC: 68W20 68W25 90C27 PDF BibTeX XML Cite \textit{P. Manurangsi} and \textit{L. Trevisan}, LIPIcs -- Leibniz Int. Proc. Inform. 116, Article 20, 17 p. (2018; Zbl 07378632) Full Text: DOI OpenURL
Dinur, Irit; Manurangsi, Pasin ETH-hardness of approximating 2-CSPs and directed Steiner network. (English) Zbl 1462.68068 Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 36, 20 p. (2018). MSC: 68Q17 68Q27 68R10 68W25 PDF BibTeX XML Cite \textit{I. Dinur} and \textit{P. Manurangsi}, LIPIcs -- Leibniz Int. Proc. Inform. 94, Article 36, 20 p. (2018; Zbl 1462.68068) Full Text: DOI arXiv OpenURL
Gur, Tom; Ramnarayan, Govind; Rothblum, Ron D. Relaxed locally correctable codes. (English) Zbl 1462.68050 Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 27, 11 p. (2018). MSC: 68Q10 68P30 PDF BibTeX XML Cite \textit{T. Gur} et al., LIPIcs -- Leibniz Int. Proc. Inform. 94, Article 27, 11 p. (2018; Zbl 1462.68050) Full Text: DOI OpenURL
Srinivasan, Srikanth; Sudan, Madhu Local decoding and testing of polynomials over grids. (English) Zbl 1462.68052 Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 26, 14 p. (2018). MSC: 68Q10 68P30 68W20 94B35 PDF BibTeX XML Cite \textit{S. Srinivasan} and \textit{M. Sudan}, LIPIcs -- Leibniz Int. Proc. Inform. 94, Article 26, 14 p. (2018; Zbl 1462.68052) Full Text: DOI OpenURL
Guruswami, Venkatesan; Saket, Rishi Hardness of rainbow coloring hypergraphs. (English) Zbl 07278105 Lokam, Satya (ed.) et al., 37th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2017, IIT Kanpur, India, December 12–14, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 93, Article 33, 15 p. (2018). MSC: 68R10 05C15 05C65 06E30 68Q17 PDF BibTeX XML Cite \textit{V. Guruswami} and \textit{R. Saket}, LIPIcs -- Leibniz Int. Proc. Inform. 93, Article 33, 15 p. (2018; Zbl 07278105) Full Text: DOI OpenURL
Bhangale, Amey; Khot, Subhash; Thiruvenkatachari, Devanathan An improved dictatorship test with perfect completeness. (English) Zbl 07278087 Lokam, Satya (ed.) et al., 37th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2017, IIT Kanpur, India, December 12–14, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 93, Article 15, 23 p. (2018). MSC: 68Q25 06E30 68W20 PDF BibTeX XML Cite \textit{A. Bhangale} et al., LIPIcs -- Leibniz Int. Proc. Inform. 93, Article 15, 23 p. (2018; Zbl 07278087) Full Text: DOI arXiv OpenURL
Kiyoshima, Susumu No-signaling linear PCPs. (English) Zbl 1443.94068 Beimel, Amos (ed.) et al., Theory of cryptography. 16th international conference, TCC 2018, Panaji, India, November 11–14, 2018. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 11239, 67-97 (2018). MSC: 94A60 PDF BibTeX XML Cite \textit{S. Kiyoshima}, Lect. Notes Comput. Sci. 11239, 67--97 (2018; Zbl 1443.94068) Full Text: DOI OpenURL
Chandrasekaran, Karthekeyan; Cheraghchi, Mahdi; Gandikota, Venkata; Grigorescu, Elena Local testing of lattices. (English) Zbl 1422.11147 SIAM J. Discrete Math. 32, No. 2, 1265-1295 (2018). MSC: 11H31 94B05 PDF BibTeX XML Cite \textit{K. Chandrasekaran} et al., SIAM J. Discrete Math. 32, No. 2, 1265--1295 (2018; Zbl 1422.11147) Full Text: DOI OpenURL
Applebaum, Benny; Lovett, Shachar Algebraic attacks against random local functions and their countermeasures. (English) Zbl 1417.94039 SIAM J. Comput. 47, No. 1, 52-79 (2018). MSC: 94A60 PDF BibTeX XML Cite \textit{B. Applebaum} and \textit{S. Lovett}, SIAM J. Comput. 47, No. 1, 52--79 (2018; Zbl 1417.94039) Full Text: DOI OpenURL
Chiesa, Alessandro; Manohar, Peter; Shinkar, Igor On axis-parallel tests for tensor product codes. (English) Zbl 1467.68211 Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 39, 22 p. (2017). MSC: 68W20 68P30 94B05 94B25 PDF BibTeX XML Cite \textit{A. Chiesa} et al., LIPIcs -- Leibniz Int. Proc. Inform. 81, Article 39, 22 p. (2017; Zbl 1467.68211) Full Text: DOI OpenURL
Manurangsi, Pasin Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis. (English) Zbl 1461.68160 Algorithms (Basel) 11, No. 1, Paper No. 10, 22 p. (2017). MSC: 68R10 68Q17 PDF BibTeX XML Cite \textit{P. Manurangsi}, Algorithms (Basel) 11, No. 1, Paper No. 10, 22 p. (2017; Zbl 1461.68160) Full Text: DOI arXiv OpenURL
Bavarian, Mohammad; Vidick, Thomas; Yuen, Henry Parallel repetition via fortification: analytic view and the quantum case. (English) Zbl 1402.91028 Papadimitriou, Christos H. (ed.), 8th innovations in theoretical computer science conference, ITCS 2017, Berkeley, CA, USA, January 9–11, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-029-3). LIPIcs – Leibniz International Proceedings in Informatics 67, Article 22, 33 p. (2017). MSC: 91A20 81P40 81P45 91A05 91A06 91A12 91A80 PDF BibTeX XML Cite \textit{M. Bavarian} et al., LIPIcs -- Leibniz Int. Proc. Inform. 67, Article 22, 33 p. (2017; Zbl 1402.91028) Full Text: DOI arXiv OpenURL
Briët, Jop; Dvir, Zeev; Gopi, Sivakanth Outlaw distributions and locally decodable codes. (English) Zbl 1402.94121 Papadimitriou, Christos H. (ed.), 8th innovations in theoretical computer science conference, ITCS 2017, Berkeley, CA, USA, January 9–11, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-029-3). LIPIcs – Leibniz International Proceedings in Informatics 67, Article 20, 19 p. (2017). MSC: 94B35 68Q17 68Q87 PDF BibTeX XML Cite \textit{J. Briët} et al., LIPIcs -- Leibniz Int. Proc. Inform. 67, Article 20, 19 p. (2017; Zbl 1402.94121) Full Text: DOI arXiv OpenURL
Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Goldwasser, Shafi; Lin, Huijia; Rubinstein, Aviad; Tromer, Eran The hunting of the SNARK. (English) Zbl 1386.94066 J. Cryptology 30, No. 4, 989-1066 (2017). MSC: 94A60 68Q05 68Q10 PDF BibTeX XML Cite \textit{N. Bitansky} et al., J. Cryptology 30, No. 4, 989--1066 (2017; Zbl 1386.94066) Full Text: DOI OpenURL
Liu, Xiaomei; Ge, Shuzhi Sam; Goh, Cher-Hiang Formation potential field for trajectory tracking control of multi-agents in constrained space. (English) Zbl 1380.93015 Int. J. Control 90, No. 10, 2137-2151 (2017). MSC: 93A14 68T42 93D30 93C15 93C10 PDF BibTeX XML Cite \textit{X. Liu} et al., Int. J. Control 90, No. 10, 2137--2151 (2017; Zbl 1380.93015) Full Text: DOI OpenURL
Moshkovitz, Dana Low-degree test with polynomially small error. (English) Zbl 1378.68052 Comput. Complexity 26, No. 3, 531-582 (2017). MSC: 68Q17 68Q25 68W20 PDF BibTeX XML Cite \textit{D. Moshkovitz}, Comput. Complexity 26, No. 3, 531--582 (2017; Zbl 1378.68052) Full Text: DOI OpenURL
David, Roee; Dinur, Irit; Goldenberg, Elazar; Kindler, Guy; Shinkar, Igor Direct sum testing. (English) Zbl 1371.68322 SIAM J. Comput. 46, No. 4, 1336-1369 (2017). MSC: 68W20 68Q25 PDF BibTeX XML Cite \textit{R. David} et al., SIAM J. Comput. 46, No. 4, 1336--1369 (2017; Zbl 1371.68322) Full Text: DOI OpenURL
Ben-Sasson, Eli; Bentov, Iddo; Chiesa, Alessandro; Gabizon, Ariel; Genkin, Daniel; Hamilis, Matan; Pergament, Evgenya; Riabzev, Michael; Silberstein, Mark; Tromer, Eran; Virza, Madars Computational integrity with a public random string from quasi-linear PCPs. (English) Zbl 1415.94409 Coron, Jean-Sébastien (ed.) et al., Advances in cryptology – EUROCRYPT 2017. 36th annual international conference on the theory and applications of cryptographic techniques, Paris, France, April 30 – May 4, 2017. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 10212, 551-579 (2017). MSC: 94A60 PDF BibTeX XML Cite \textit{E. Ben-Sasson} et al., Lect. Notes Comput. Sci. 10212, 551--579 (2017; Zbl 1415.94409) Full Text: DOI OpenURL
Brandão, Fernando G. S. L.; Harrow, Aram W. Quantum de Finetti theorems under local measurements with applications. (English) Zbl 1380.81068 Commun. Math. Phys. 353, No. 2, 469-506 (2017). Reviewer: Hichem Eleuch (College Station) MSC: 81P45 81P40 81P15 62C12 PDF BibTeX XML Cite \textit{F. G. S. L. Brandão} and \textit{A. W. Harrow}, Commun. Math. Phys. 353, No. 2, 469--506 (2017; Zbl 1380.81068) Full Text: DOI arXiv Link OpenURL
Baartse, Martijn; Meer, Klaus An algebraic proof of the real number PCP theorem. (English) Zbl 1370.68105 J. Complexity 40, 34-77 (2017). MSC: 68Q15 03D78 68Q05 PDF BibTeX XML Cite \textit{M. Baartse} and \textit{K. Meer}, J. Complexity 40, 34--77 (2017; Zbl 1370.68105) Full Text: DOI OpenURL
Manurangsi, Pasin; Moshkovitz, Dana Improved approximation algorithms for projection games. (English) Zbl 1359.68316 Algorithmica 77, No. 2, 555-594 (2017). MSC: 68W25 68Q17 91A43 PDF BibTeX XML Cite \textit{P. Manurangsi} and \textit{D. Moshkovitz}, Algorithmica 77, No. 2, 555--594 (2017; Zbl 1359.68316) Full Text: DOI arXiv OpenURL
Çivril, A. Sparse approximation is provably hard under coherent dictionaries. (English) Zbl 1354.65085 J. Comput. Syst. Sci. 84, 32-43 (2017). MSC: 65F50 65Y20 68Q17 PDF BibTeX XML Cite \textit{A. Çivril}, J. Comput. Syst. Sci. 84, 32--43 (2017; Zbl 1354.65085) Full Text: DOI arXiv OpenURL
Rosicka, M.; Ramanathan, R.; Gnaciński, P.; Horodecki, K.; Horodecki, M.; Horodecki, P.; Severini, S. Linear game non-contextuality and Bell inequalities – a graph-theoretic approach. (English) Zbl 1456.81019 New J. Phys. 18, No. 4, Article ID 045020, 22 p. (2016). MSC: 81P13 81P15 91A05 PDF BibTeX XML Cite \textit{M. Rosicka} et al., New J. Phys. 18, No. 4, Article ID 045020, 22 p. (2016; Zbl 1456.81019) Full Text: DOI arXiv OpenURL
Ben-Sasson, Eli; Chiesa, Alessandro; Spooner, Nicholas Interactive oracle proofs. (English) Zbl 1397.94048 Hirt, Martin (ed.) et al., Theory of cryptography. 14th international conference, TCC 2016-B, Beijing, China, October 31 – November 3, 2016, Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-53643-8/pbk; 978-3-662-53644-5/ebook). Lecture Notes in Computer Science 9986, 31-60 (2016). MSC: 94A60 PDF BibTeX XML Cite \textit{E. Ben-Sasson} et al., Lect. Notes Comput. Sci. 9986, 31--60 (2016; Zbl 1397.94048) Full Text: DOI OpenURL
Ben-Sasson, Eli; Viderman, Michael A combinatorial characterization of smooth LTCs and applications. (English) Zbl 1409.94921 Random Struct. Algorithms 49, No. 2, 280-307 (2016). MSC: 94B05 PDF BibTeX XML Cite \textit{E. Ben-Sasson} and \textit{M. Viderman}, Random Struct. Algorithms 49, No. 2, 280--307 (2016; Zbl 1409.94921) Full Text: DOI OpenURL
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 PDF BibTeX XML Cite \textit{T. Vidick}, SIAM J. Comput. 45, No. 3, 1007--1063 (2016; Zbl 1342.81080) Full Text: DOI arXiv Link OpenURL
Grilo, Alex Bredariol; Kerenidis, Iordanis; Sikora, Jamie QMA with subset state witnesses. (English) Zbl 1356.68081 Chic. J. Theor. Comput. Sci. 2016, Article No. 4, 17 p. (2016). MSC: 68Q15 68Q12 PDF BibTeX XML Cite \textit{A. B. Grilo} et al., Chic. J. Theor. Comput. Sci. 2016, Article No. 4, 17 p. (2016; Zbl 1356.68081) Full Text: DOI OpenURL
Kol, Gillat; Raz, Ran Bounds on 2-query locally testable codes with affine tests. (English) Zbl 1357.68051 Inf. Process. Lett. 116, No. 8, 521-525 (2016). MSC: 68P30 68Q25 94B60 94B65 PDF BibTeX XML Cite \textit{G. Kol} and \textit{R. Raz}, Inf. Process. Lett. 116, No. 8, 521--525 (2016; Zbl 1357.68051) Full Text: DOI Link OpenURL
Ben-Sasson, Eli; Chiesa, Alessandro; Gabizon, Ariel; Virza, Madars Quasi-linear size zero knowledge from linear-algebraic PCPs. (English) Zbl 1375.94101 Kushilevitz, Eyal (ed.) et al., Theory of cryptography. 13th international conference, TCC 2016-A, Tel Aviv, Israel, January 10–13, 2016. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-49098-3/pbk; 978-3-662-49099-0/ebook). Lecture Notes in Computer Science 9563, 33-64 (2016). MSC: 94A60 68Q15 PDF BibTeX XML Cite \textit{E. Ben-Sasson} et al., Lect. Notes Comput. Sci. 9563, 33--64 (2016; Zbl 1375.94101) Full Text: DOI OpenURL
Meir, Or Combinatorial PCPs with short proofs. (English) Zbl 1336.68090 Comput. Complexity 25, No. 1, 1-102 (2016). MSC: 68Q15 PDF BibTeX XML Cite \textit{O. Meir}, Comput. Complexity 25, No. 1, 1--102 (2016; Zbl 1336.68090) Full Text: DOI OpenURL
Brandão, Fernando G. S. L.; Harrow, Aram W. Product-state approximations to quantum states. (English) Zbl 1333.81447 Commun. Math. Phys. 342, No. 1, 47-80 (2016). MSC: 81V70 81P40 82C22 PDF BibTeX XML Cite \textit{F. G. S. L. Brandão} and \textit{A. W. Harrow}, Commun. Math. Phys. 342, No. 1, 47--80 (2016; Zbl 1333.81447) Full Text: DOI arXiv OpenURL
Tamaki, Suguru Parallel repetition of two-prover one-round games: an exposition. (English) Zbl 1484.68063 Interdiscip. Inf. Sci. 21, No. 4, 289-306 (2015). MSC: 68Q10 05C50 68Q17 68Q25 90C27 91A80 PDF BibTeX XML Cite \textit{S. Tamaki}, Interdiscip. Inf. Sci. 21, No. 4, 289--306 (2015; Zbl 1484.68063) Full Text: DOI OpenURL
Kobayashi, Hirotada; Le Gall, François; Nishimura, Harumichi Stronger methods of making quantum interactive proofs perfectly complete. (English) Zbl 1357.68071 SIAM J. Comput. 44, No. 2, 243-289 (2015). MSC: 68Q12 81P68 PDF BibTeX XML Cite \textit{H. Kobayashi} et al., SIAM J. Comput. 44, No. 2, 243--289 (2015; Zbl 1357.68071) Full Text: DOI arXiv OpenURL
Goldreich, Oded; Meir, Or Input-oblivious proof systems and a uniform complexity perspective on P/poly. (English) Zbl 1347.68160 ACM Trans. Comput. Theory 7, No. 4, Article No. 16, 13 p. (2015). MSC: 68Q15 68Q10 PDF BibTeX XML Cite \textit{O. Goldreich} and \textit{O. Meir}, ACM Trans. Comput. Theory 7, No. 4, Article No. 16, 13 p. (2015; Zbl 1347.68160) Full Text: DOI Link OpenURL
Regev, Oded; Vidick, Thomas Quantum XOR games. (English) Zbl 1348.81177 ACM Trans. Comput. Theory 7, No. 4, Article No. 15, 43 p. (2015). MSC: 81P68 81P40 91A80 PDF BibTeX XML Cite \textit{O. Regev} and \textit{T. Vidick}, ACM Trans. Comput. Theory 7, No. 4, Article No. 15, 43 p. (2015; Zbl 1348.81177) Full Text: DOI arXiv OpenURL
Khachay, Michael Committee polyhedral separability: complexity and polynomial approximation. (English) Zbl 1343.68198 Mach. Learn. 101, No. 1-3, 231-251 (2015). MSC: 68T05 62H30 68U05 68W25 90C27 PDF BibTeX XML Cite \textit{M. Khachay}, Mach. Learn. 101, No. 1--3, 231--251 (2015; Zbl 1343.68198) Full Text: DOI OpenURL
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 PDF BibTeX XML Cite \textit{D. Aharonov} and \textit{L. Eldar}, SIAM J. Comput. 44, No. 5, 1230--1262 (2015; Zbl 1326.81054) Full Text: DOI arXiv OpenURL
Coudron, Matthew; Vidick, Thomas Interactive proofs with approximately commuting provers. (English) Zbl 1441.68088 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 355-366 (2015). MSC: 68Q25 81P40 81P68 94A60 PDF BibTeX XML Cite \textit{M. Coudron} and \textit{T. Vidick}, Lect. Notes Comput. Sci. 9134, 355--366 (2015; Zbl 1441.68088) Full Text: DOI arXiv Link OpenURL
Bhangale, Amey; Kopparty, Swastik; Sachdeva, Sushant Simultaneous approximation of constraint satisfaction problems. (English) Zbl 1403.68341 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-47671-0/pbk; 978-3-662-47672-7/ebook). Lecture Notes in Computer Science 9134, 193-205 (2015). MSC: 68W25 68Q25 PDF BibTeX XML Cite \textit{A. Bhangale} et al., Lect. Notes Comput. Sci. 9134, 193--205 (2015; Zbl 1403.68341) Full Text: DOI arXiv OpenURL
Tamaki, Suguru; Yoshida, Yuichi A query efficient non-adaptive long code test with perfect completeness. (English) Zbl 1341.68066 Random Struct. Algorithms 47, No. 2, 386-406 (2015). MSC: 68Q25 68W20 68W25 PDF BibTeX XML Cite \textit{S. Tamaki} and \textit{Y. Yoshida}, Random Struct. Algorithms 47, No. 2, 386--406 (2015; Zbl 1341.68066) Full Text: DOI Link OpenURL
Chiesa, Alessandro; Zhu, Zeyuan Allen Shorter arithmetization of nondeterministic computations. (English) Zbl 1430.68108 Theor. Comput. Sci. 600, 107-131 (2015). MSC: 68Q04 68Q09 68Q10 68Q17 68Q25 PDF BibTeX XML Cite \textit{A. Chiesa} and \textit{Z. A. Zhu}, Theor. Comput. Sci. 600, 107--131 (2015; Zbl 1430.68108) Full Text: DOI OpenURL
Baartse, Martijn; Meer, Klaus The PCP theorem for NP over the reals. (English) Zbl 1327.68107 Found. Comput. Math. 15, No. 3, 651-680 (2015). MSC: 68Q15 03D78 PDF BibTeX XML Cite \textit{M. Baartse} and \textit{K. Meer}, Found. Comput. Math. 15, No. 3, 651--680 (2015; Zbl 1327.68107) Full Text: DOI Link OpenURL
Cooney, T.; Junge, M.; Palazuelos, C.; Pérez-García, D. Rank-one quantum games. (English) Zbl 1328.81063 Comput. Complexity 24, No. 1, 133-196 (2015). Reviewer: Ahmed Hegazi (Mansoura) MSC: 81P45 91A05 81P40 68Q25 47L25 PDF BibTeX XML Cite \textit{T. Cooney} et al., Comput. Complexity 24, No. 1, 133--196 (2015; Zbl 1328.81063) Full Text: DOI arXiv Link OpenURL
Viderman, Michael A combination of testability and decodability by tensor products. (English) Zbl 1316.94112 Random Struct. Algorithms 46, No. 3, 572-598 (2015). MSC: 94B05 94B35 PDF BibTeX XML Cite \textit{M. Viderman}, Random Struct. Algorithms 46, No. 3, 572--598 (2015; Zbl 1316.94112) Full Text: DOI Link OpenURL
Aharonov, Dorit; Eldar, Lior The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\). (English) Zbl 1327.68105 Quantum Inf. Process. 14, No. 1, 83-101 (2015). MSC: 68Q12 68Q17 81P68 81Q35 PDF BibTeX XML Cite \textit{D. Aharonov} and \textit{L. Eldar}, Quantum Inf. Process. 14, No. 1, 83--101 (2015; Zbl 1327.68105) Full Text: DOI arXiv OpenURL
Kopparty, Swastik; Saraf, Shubhangi; Yekhanin, Sergey High-rate codes with sublinear-time decoding. (English) Zbl 1321.94138 J. ACM 61, No. 5, Article No. 28, 20 p. (2014). MSC: 94B35 68Q25 68P30 PDF BibTeX XML Cite \textit{S. Kopparty} et al., J. ACM 61, No. 5, Article No. 28, 20 p. (2014; Zbl 1321.94138) Full Text: DOI OpenURL
Boros, Endre; Gruber, Aritanan Hardness results for approximate pure Horn CNF formulae minimization. (English) Zbl 1320.68089 Ann. Math. Artif. Intell. 71, No. 4, 327-363 (2014). MSC: 68Q17 06E30 68T27 PDF BibTeX XML Cite \textit{E. Boros} and \textit{A. Gruber}, Ann. Math. Artif. Intell. 71, No. 4, 327--363 (2014; Zbl 1320.68089) Full Text: DOI arXiv OpenURL
Meir, Or Combinatorial PCPs with efficient verifiers. (English) Zbl 1318.68087 Comput. Complexity 23, No. 3, 355-478 (2014). MSC: 68Q15 PDF BibTeX XML Cite \textit{O. Meir}, Comput. Complexity 23, No. 3, 355--478 (2014; Zbl 1318.68087) Full Text: DOI Link OpenURL
Barenboim, Leonid; Elkin, Michael Combinatorial algorithms for distributed graph coloring. (English) Zbl 1291.68426 Distrib. Comput. 27, No. 2, 79-93 (2014). MSC: 68W15 05C15 05C85 PDF BibTeX XML Cite \textit{L. Barenboim} and \textit{M. Elkin}, Distrib. Comput. 27, No. 2, 79--93 (2014; Zbl 1291.68426) Full Text: DOI Link OpenURL
Dekel, Yael; Gurel-Gurevich, Ori; Peres, Yuval Finding hidden cliques in linear time with high probability. (English) Zbl 1290.05129 Comb. Probab. Comput. 23, No. 1, 29-49 (2014). Reviewer: David B. Penman (Colchester) MSC: 05C80 05C85 68W20 PDF BibTeX XML Cite \textit{Y. Dekel} et al., Comb. Probab. Comput. 23, No. 1, 29--49 (2014; Zbl 1290.05129) Full Text: DOI arXiv OpenURL
Çivril, A. Column subset selection problem is UG-hard. (English) Zbl 1285.68052 J. Comput. Syst. Sci. 80, No. 4, 849-859 (2014). MSC: 68Q17 65F30 PDF BibTeX XML Cite \textit{A. Çivril}, J. Comput. Syst. Sci. 80, No. 4, 849--859 (2014; Zbl 1285.68052) Full Text: DOI OpenURL
Shahinpour, Shahram; Butenko, Sergiy Distance-based clique relaxations in networks: \(s\)-clique and \(s\)-club. (English) Zbl 1344.90064 Goldengorin, Boris I. (ed.) et al., Models, algorithms, and technologies for network analysis. Proceedings of the second international conference on network analysis, Nizhny Novgorod, Russia, May 7–9, 2012. New York, NY: Springer (ISBN 978-1-4614-8587-2/hbk; 978-1-4614-8588-9/ebook). Springer Proceedings in Mathematics & Statistics 59, 149-174 (2013). MSC: 90C35 05C85 PDF BibTeX XML Cite \textit{S. Shahinpour} and \textit{S. Butenko}, Springer Proc. Math. Stat. 59, 149--174 (2013; Zbl 1344.90064) Full Text: DOI OpenURL
Canetti, Ran; Riva, Ben; Rothblum, Guy N. Refereed delegation of computation. (English) Zbl 1290.68013 Inf. Comput. 226, 16-36 (2013). MSC: 68M12 91A80 PDF BibTeX XML Cite \textit{R. Canetti} et al., Inf. Comput. 226, 16--36 (2013; Zbl 1290.68013) Full Text: DOI OpenURL
Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu 2-transitivity is insufficient for local testability. (English) Zbl 1283.94130 Comput. Complexity 22, No. 1, 137-158 (2013). Reviewer: Adrian Atanasiu (Bucureşti) MSC: 94B15 68W20 68Q25 11T71 PDF BibTeX XML Cite \textit{E. Grigorescu} et al., Comput. Complexity 22, No. 1, 137--158 (2013; Zbl 1283.94130) Full Text: DOI OpenURL
Çivril, Ali; Magdon-Ismail, Malik Exponential inapproximability of selecting a maximum volume sub-matrix. (English) Zbl 1259.68086 Algorithmica 65, No. 1, 159-176 (2013). MSC: 68Q25 68Q17 PDF BibTeX XML Cite \textit{A. Çivril} and \textit{M. Magdon-Ismail}, Algorithmica 65, No. 1, 159--176 (2013; Zbl 1259.68086) Full Text: DOI arXiv OpenURL
Cheriyan, Joseph; Laekhanukit, Bundit; Naves, Guyslain; Vetta, Adrian Approximating rooted Steiner networks. (English) Zbl 1421.68202 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1499-1511 (2012). MSC: 68W25 05C40 68Q17 68R10 PDF BibTeX XML Cite \textit{J. Cheriyan} et al., in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1499--1511 (2012; Zbl 1421.68202) Full Text: Link OpenURL
Chuzhoy, Julia; Makarychev, Yury; Vijayaraghavan, Aravindan; Zhou, Yuan Approximation algorithms and hardness of the \(k\)-route cut problem. (English) Zbl 1421.68204 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 780-799 (2012). MSC: 68W25 68Q17 68R10 68Q25 PDF BibTeX XML Cite \textit{J. Chuzhoy} et al., in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 780--799 (2012; Zbl 1421.68204) Full Text: Link OpenURL
Nicosia, Vincenzo; Tang, John; Musolesi, Mirco; Russo, Giovanni; Mascolo, Cecilia; Latora, Vito Components in time-varying graphs. (English) Zbl 1331.68156 Chaos 22, No. 2, 023101, 11 p. (2012). MSC: 68R10 05C20 05C40 05C82 05C90 PDF BibTeX XML Cite \textit{V. Nicosia} et al., Chaos 22, No. 2, 023101, 11 p. (2012; Zbl 1331.68156) Full Text: DOI OpenURL
Ben-Sasson, Eli; Viderman, Michael Towards lower bounds on locally testable codes via density arguments. (English) Zbl 1302.94064 Comput. Complexity 21, No. 2, 267-309 (2012). MSC: 94B05 94B65 PDF BibTeX XML Cite \textit{E. Ben-Sasson} and \textit{M. Viderman}, Comput. Complexity 21, No. 2, 267--309 (2012; Zbl 1302.94064) Full Text: DOI OpenURL
Li, Angsheng; Pan, Yicheng Characterizations of locally testable linear- and affine-invariant families. (English) Zbl 1235.94066 Theor. Comput. Sci. 414, No. 1, 55-75 (2012). MSC: 94B25 11T71 68W30 PDF BibTeX XML Cite \textit{A. Li} and \textit{Y. Pan}, Theor. Comput. Sci. 414, No. 1, 55--75 (2012; Zbl 1235.94066) Full Text: DOI OpenURL
Kamath, Suresh Unrelated parallel machine scheduling – perspectives and progress. (English) Zbl 1353.90064 Opsearch 48, No. 4, 318-334 (2011). MSC: 90B35 68W10 PDF BibTeX XML Cite \textit{S. Kamath}, Opsearch 48, No. 4, 318--334 (2011; Zbl 1353.90064) Full Text: DOI OpenURL
Alekhnovich, Michael More on average case vs approximation complexity. (English) Zbl 1242.68109 Comput. Complexity 20, No. 4, 755-786 (2011). MSC: 68Q17 68Q30 68W25 03F20 68Q10 94A60 PDF BibTeX XML Cite \textit{M. Alekhnovich}, Comput. Complexity 20, No. 4, 755--786 (2011; Zbl 1242.68109) Full Text: DOI OpenURL
Yamamoto, Go; Kobayashi, Tetsutaro Self-correctors for cryptographic modules. (English) Zbl 1292.68064 Chen, Liqun (ed.), Cryptography and coding. 13th IMA international conference, IMACC 2011, Oxford, UK, December 12–15, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25515-1/pbk). Lecture Notes in Computer Science 7089, 132-151 (2011). MSC: 68P30 94A60 PDF BibTeX XML Cite \textit{G. Yamamoto} and \textit{T. Kobayashi}, Lect. Notes Comput. Sci. 7089, 132--151 (2011; Zbl 1292.68064) Full Text: DOI OpenURL
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel PCP characterizations of NP: toward a polynomially-small error-probability. (English) Zbl 1234.68133 Comput. Complexity 20, No. 3, 413-504 (2011). MSC: 68Q17 68Q15 PDF BibTeX XML Cite \textit{I. Dinur} et al., Comput. Complexity 20, No. 3, 413--504 (2011; Zbl 1234.68133) Full Text: DOI OpenURL
Dinur, Irit; Meir, Or Derandomized parallel repetition via structured PCPs. (English) Zbl 1255.68068 Comput. Complexity 20, No. 2, 207-327 (2011). MSC: 68Q15 PDF BibTeX XML Cite \textit{I. Dinur} and \textit{O. Meir}, Comput. Complexity 20, No. 2, 207--327 (2011; Zbl 1255.68068) Full Text: DOI OpenURL
Barenboim, Leonid; Elkin, Michael Combinatorial algorithms for distributed graph coloring. (English) Zbl 1350.68277 Peleg, David (ed.), Distributed computing. 25th international symposium, DISC 2011, Rome, Italy, September 20–22, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24099-7/pbk). Lecture Notes in Computer Science 6950, 66-81 (2011). MSC: 68W15 05C15 05C69 05C85 68R10 PDF BibTeX XML Cite \textit{L. Barenboim} and \textit{M. Elkin}, Lect. Notes Comput. Sci. 6950, 66--81 (2011; Zbl 1350.68277) Full Text: DOI Link OpenURL
Meer, Klaus Almost transparent short proofs for \(\mathrm{NP}_{\mathbb R}\). (English) Zbl 1342.68138 Owe, Olaf (ed.) et al., Fundamentals of computation theory. 18th international symposium, FCT 2011, Oslo, Norway, August 22–25, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22952-7/pbk). Lecture Notes in Computer Science 6914, 41-52 (2011). MSC: 68Q15 03D78 68Q05 PDF BibTeX XML Cite \textit{K. Meer}, Lect. Notes Comput. Sci. 6914, 41--52 (2011; Zbl 1342.68138) Full Text: DOI OpenURL
Goldreich, Oded Randomness and computation. (English) Zbl 1343.68181 Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 507-539 (2011). MSC: 68Q87 68Q15 68W20 94A60 PDF BibTeX XML Cite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 507--539 (2011; Zbl 1343.68181) Full Text: DOI Link OpenURL
Goldreich, Oded Bravely, moderately: a common theme in four recent works. (English) Zbl 1343.68113 Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 373-389 (2011). MSC: 68Q25 05C85 68Q15 68W25 PDF BibTeX XML Cite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 373--389 (2011; Zbl 1343.68113) Full Text: DOI OpenURL
Goldreich, Oded Short locally testable codes and proofs. (English) Zbl 1309.68220 Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 333-372 (2011). MSC: 68W20 68P30 68Q25 68Q60 94B60 PDF BibTeX XML Cite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 333--372 (2011; Zbl 1309.68220) Full Text: DOI OpenURL
Goldreich, Oded Using the FGLSS-reduction to prove inapproximability results for minimum vertex cover in hypergraphs. (English) Zbl 1343.68094 Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 88-97 (2011). MSC: 68Q17 05C65 05C70 90C27 PDF BibTeX XML Cite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 88--97 (2011; Zbl 1343.68094) Full Text: DOI OpenURL
Ben-Sasson, Eli; Sudan, Madhu Limits on the rate of locally testable affine-invariant codes. (English) Zbl 1343.68288 Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 412-423 (2011). MSC: 68W20 94B60 PDF BibTeX XML Cite \textit{E. Ben-Sasson} and \textit{M. Sudan}, Lect. Notes Comput. Sci. 6845, 412--423 (2011; Zbl 1343.68288) Full Text: DOI Link OpenURL
Ben-Sasson, Eli; Grigorescu, Elena; Maatouk, Ghid; Shpilka, Amir; Sudan, Madhu On sums of locally testable affine invariant properties. (English) Zbl 1343.68287 Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 400-411 (2011). MSC: 68W20 11T71 PDF BibTeX XML Cite \textit{E. Ben-Sasson} et al., Lect. Notes Comput. Sci. 6845, 400--411 (2011; Zbl 1343.68287) Full Text: DOI Link OpenURL
Sachdeva, Sushant; Saket, Rishi Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs. (English) Zbl 1343.68100 Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 327-338 (2011). MSC: 68Q17 05C65 05C70 PDF BibTeX XML Cite \textit{S. Sachdeva} and \textit{R. Saket}, Lect. Notes Comput. Sci. 6845, 327--338 (2011; Zbl 1343.68100) Full Text: DOI arXiv OpenURL
Håstad, Johan Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\). (English) Zbl 1343.68312 Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 242-253 (2011). MSC: 68W25 11T06 68Q17 68W20 PDF BibTeX XML Cite \textit{J. Håstad}, Lect. Notes Comput. Sci. 6845, 242--253 (2011; Zbl 1343.68312) Full Text: DOI OpenURL
Martinhon, Carlos; Protti, Fábio An improved derandomized approximation algorithm for the max-controlled set problem. (English) Zbl 1218.68196 RAIRO, Theor. Inform. Appl. 45, No. 2, 181-196 (2011). MSC: 68W20 68W25 PDF BibTeX XML Cite \textit{C. Martinhon} and \textit{F. Protti}, RAIRO, Theor. Inform. Appl. 45, No. 2, 181--196 (2011; Zbl 1218.68196) Full Text: DOI Numdam EuDML OpenURL
Austrin, Per; Khot, Subhash A simple deterministic reduction for the gap minimum distance of code problem. (English) Zbl 1334.68082 Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 474-485 (2011). MSC: 68Q17 94B05 PDF BibTeX XML Cite \textit{P. Austrin} and \textit{S. Khot}, Lect. Notes Comput. Sci. 6755, 474--485 (2011; Zbl 1334.68082) Full Text: DOI arXiv OpenURL
Das Sarma, Atish; Lipton, Richard J.; Nanongkai, Danupon Best-order streaming model. (English) Zbl 1216.68108 Theor. Comput. Sci. 412, No. 23, 2544-2555 (2011). MSC: 68Q05 05C40 05C70 68Q25 PDF BibTeX XML Cite \textit{A. Das Sarma} et al., Theor. Comput. Sci. 412, No. 23, 2544--2555 (2011; Zbl 1216.68108) Full Text: DOI OpenURL