×

Found 141 Documents (Results 1–100)

100
MathJax

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI arXiv

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
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI

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
Full Text: DOI arXiv

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
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI

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
Full Text: DOI

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
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

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
Full Text: DOI arXiv

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
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: Link

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).
PDF BibTeX XML Cite
Full Text: Link

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
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI Link

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
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI Link

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).
PDF BibTeX XML Cite
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI

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).
PDF BibTeX XML Cite
Full Text: DOI

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
Full Text: DOI Link

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
Full Text: DOI Link

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
Full Text: DOI arXiv

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).
PDF BibTeX XML Cite
Full Text: DOI

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
Full Text: DOI arXiv

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Year of Publication

all top 3

Classification

all top 3

Software