×

Found 214 Documents (Results 1–100)

100
MathJax
Newest 1st
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
  • logo of hbz
  • logo of WorldCat
Arunachaleswaran, Eshwar Ram; Barman, Siddharth; Kumar, Rachitesh; Rathi, Nidhi

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).
MSC:  91B32 68Q17 68W25 91B15
PDF BibTeX XML Cite
\textit{E. R. Arunachaleswaran} et al., Lect. Notes Comput. Sci. 11920, 57--70 (2019; Zbl 1435.91103)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat
Atserias, Albert; Dawar, Anuj

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
\textit{A. Atserias} and \textit{A. Dawar}, LIPIcs -- Leibniz Int. Proc. Inform. 119, Article 7, 21 p. (2018; Zbl 07533332)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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:  68N30 68Qxx
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
  • logo of hbz
  • logo of WorldCat
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:  68N30 68Qxx
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
Ding, Wei; Qiu, Ke

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
\textit{W. Ding} and \textit{K. Qiu}, Lect. Notes Comput. Sci. 10043, 408--420 (2016; Zbl 1483.90074)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
Mukhopadhyay, Partha

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).
MSC:  68Q06 13P05 14Q20 68Q25 68W20
PDF BibTeX XML Cite
\textit{P. Mukhopadhyay}, Lect. Notes Comput. Sci. 9691, 309--323 (2016; Zbl 1476.68085)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat
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
  • logo of hbz
  • logo of WorldCat

Filter Results by …

Document Type

Reviewing State

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Classification

all top 3

Software