×

Found 214 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

Fair and efficient cake division with connected pieces. (English) Zbl 1435.91103

Caragiannis, Ioannis (ed.) et al., Web and Internet economics. 15th international conference, WINE 2019, New York, NY, USA, December 10–12, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11920, 57-70 (2019).
PDF BibTeX XML Cite
Full Text: DOI arXiv

Definable inapproximability: new challenges for duplicator. (English) Zbl 07533332

Ghica, Dan R. (ed.) et al., 27th EACSL annual conference on computer science logic, CSL 2018, Birmingham, United Kingdom, September 4–8, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 119, Article 7, 21 p. (2018).
MSC:  03B70
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).
MSC:  68N30 68Qxx
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:  68N30 68Qxx
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

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

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees (extended abstract). (English) Zbl 1483.90074

Chan, T-H. Hubert (ed.) et al., Combinatorial optimization and applications. 10th international conference, COCOA 2016, Hong Kong, China, December 16–18, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10043, 408-420 (2016).
MSC:  90B85 68W40 90C27
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

Depth-4 identity testing and Noether’s normalization lemma. (English) Zbl 1476.68085

Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 11th international computer science symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9–13, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9691, 309-323 (2016).
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

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Year of Publication

all top 3

Classification