×

Found 139 Documents (Results 1–100)

Some questions related to the reverse Minkowski theorem. (English) Zbl 07821716

Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 6. Sections 12–14. Berlin: European Mathematical Society (EMS). 4898-4912 (2023).
MSC:  11H06 52C07
PDFBibTeX XMLCite
Full Text: DOI

Continuous LWE. (English) Zbl 07765203

Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 694-707 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Nearly optimal embeddings of flat tori. (English) Zbl 07758345

Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 43, 14 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

The minrank of random graphs. (English) Zbl 1467.05244

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 46, 13 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

A reverse Minkowski theorem. (English) Zbl 1370.11073

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 941-953 (2017).
MSC:  11H06
PDFBibTeX XMLCite
Full Text: DOI arXiv

Pseudorandomness of ring-LWE for any ring and modulus. (English) Zbl 1370.94536

Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 461-473 (2017).
MSC:  94A60 68Q12
PDFBibTeX XMLCite
Full Text: DOI

The restricted isometry property of subsampled Fourier matrices. (English) Zbl 1379.46014

Klartag, Bo’az (ed.) et al., Geometric aspects of functional analysis. Israel seminar (GAFA) 2014–2016. Cham: Springer (ISBN 978-3-319-45281-4/pbk; 978-3-319-45282-1/ebook). Lecture Notes in Mathematics 2169, 163-179 (2017).
MSC:  94A12 15A60 60E15
PDFBibTeX XMLCite
Full Text: DOI arXiv

Efficient quantum algorithms for (gapped) group testing and junta testing. (English) Zbl 1410.68132

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 903-922 (2016).
MSC:  68Q12 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

The restricted isometry property of subsampled Fourier matrices. (English) Zbl 1439.94011

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 288-297 (2016).
MSC:  94A12 15A60 15B52
PDFBibTeX XMLCite
Full Text: DOI

Recovering short generators of principal ideals in cyclotomic rings. (English) Zbl 1371.94630

Fischlin, Marc (ed.) et al., Advances in cryptology – EUROCRYPT 2016. 35th annual international conference on the theory and applications of cryptographic techniques, Vienna, Austria, May 8–12, 2016. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-49895-8/pbk; 978-3-662-49896-5/ebook). Lecture Notes in Computer Science 9666, 559-585 (2016).
MSC:  94A60 11Y16
PDFBibTeX XMLCite
Full Text: DOI Link

On the space complexity of linear programming with preprocessing. (English) Zbl 1334.68105

Proceedings of the 7th ACM conference on innovations in theoretical computer science, ITCS’16, Cambridge, MA, USA, January 14–16, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4057-1). 293-300 (2016).
PDFBibTeX XMLCite
Full Text: DOI

The list-decoding size of Fourier-sparse Boolean functions. (English) Zbl 1378.94082

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 58-71 (2015).
MSC:  94B35 94C10 68Q25 68Q32 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Beating the random assignment on constraint satisfaction problems of bounded degree. (English) Zbl 1375.68102

Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 110-123 (2015).
MSC:  68T20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract). (English) Zbl 1321.68426

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 733-742 (2015).
MSC:  68W20 11Y16 94A60
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the lattice isomorphism problem. (English) Zbl 1421.68085

Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 391-404 (2014).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Classical hardness of learning with errors. (English) Zbl 1293.68159

Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 575-584 (2013).
MSC:  68Q25 68Q17 94A60
PDFBibTeX XMLCite
Full Text: DOI arXiv

Efficient rounding for the noncommutative Grothendieck inequality. (English) Zbl 1293.68151

Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 71-80 (2013).
MSC:  68Q17 68W25 90C22
PDFBibTeX XMLCite
Full Text: DOI Link

A toolkit for ring-LWE cryptography. (English) Zbl 1300.94082

Johansson, Thomas (ed.) et al., Advances in cryptology – EUROCRYPT 2013. 32nd annual international conference on the theory and applications of cryptographic techniques, Athens, Greece, May 26–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38347-2/pbk). Lecture Notes in Computer Science 7881, 35-54 (2013).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

An optimal lower bound on the communication complexity of gap-Hamming-distance. (English) Zbl 1288.90005

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 51-60 (2011).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quantum one-way communication can be exponentially stronger than classical communication. (English) Zbl 1288.68074

Proceedings of the 43rd annual ACM symposium on theory of computing, STOC ’11. San Jose, CA, USA, June 6–8, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0691-1). 31-40 (2011).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Better gap-Hamming lower bounds via better round elimination. (English) Zbl 1305.68091

Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 476-489 (2010).
MSC:  68Q17 68Q05
PDFBibTeX XMLCite
Full Text: DOI Link

The Euclidean distortion of flat tori. (English) Zbl 1305.68236

Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 232-245 (2010).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

Lattice enumeration using extreme pruning. (English) Zbl 1280.94056

Gilbert, Henri (ed.), Advances in cryptology – EUROCRYPT 2010. 29th annual international conference on the theory and applications of cryptographic techniques, French Riviera, May 30 – June 3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13189-9/pbk). Lecture Notes in Computer Science 6110, 257-278 (2010).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

On ideal lattices and learning with errors over rings. (English) Zbl 1279.94099

Gilbert, Henri (ed.), Advances in cryptology – EUROCRYPT 2010. 29th annual international conference on the theory and applications of cryptographic techniques, French Riviera, May 30 – June 3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13189-9/pbk). Lecture Notes in Computer Science 6110, 1-23 (2010).
PDFBibTeX XMLCite
Full Text: DOI

Lattice-based cryptography. (English) Zbl 1161.81324

Bernstein, Daniel J. (ed.) et al., Post-quantum cryptography. First international workshop PQCrypto 2006, Leuven, The Netherland, May 23–26, 2006. Selected papers. Berlin: Springer (ISBN 978-3-540-88701-0/hbk; 978-3-540-88702-7/ebook). 147-191 (2009).
MSC:  81P68 94A60
PDFBibTeX XMLCite
Full Text: DOI

Quantum SAT for a qutrit-cinquit pair is QMA\(_{1}\)-complete. (English) Zbl 1153.81465

Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 881-892 (2008).
MSC:  81P68
PDFBibTeX XMLCite
Full Text: DOI

Upper bounds on the noise threshold for fault-tolerant quantum computing. (English) Zbl 1153.81467

Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 845-856 (2008).
MSC:  81P68
PDFBibTeX XMLCite
Full Text: DOI arXiv

Impossibility of a quantum speed-up with a faulty oracle. (English) Zbl 1153.68365

Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 773-781 (2008).
MSC:  68P10 81P68
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tensor-based hardness of the shortest vector problem to within almost polynomial factors. (English) Zbl 1232.68066

STOC’07. Proceedings of the 39th annual ACM symposium on theory of computing, San Diego, CA, USA, June 11–13, 2007. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-59593-631-8). 469-477 (2007).
PDFBibTeX XMLCite

Bounded-error quantum state identification and exponential separations in communication complexity. (English) Zbl 1301.81045

Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 594-603 (2006).
MSC:  81P68 81P45 68Q05 68Q30
PDFBibTeX XMLCite
Full Text: DOI Link

Lattice problems and norm embeddings. (English) Zbl 1301.68151

Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 447-456 (2006).
MSC:  68Q17 11H06 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Conditional hardness for approximate coloring. (English) Zbl 1301.68143

Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 344-353 (2006).
MSC:  68Q17 05C15 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. (English) Zbl 1140.94365

Vaudenay, Serge (ed.), Advances in cryptology – EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28 – June 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34546-9/pbk). Lecture Notes in Computer Science 4004, 271-288 (2006).
MSC:  94A60 94A62 11T71
PDFBibTeX XMLCite
Full Text: DOI

Lattice-based cryptography. (English) Zbl 1161.94425

Dwork, Cynthia (ed.), Advances in cryptology – CRYPTO 2006. 26th annual international cryptology conference, Santa Barbara, California, USA, August 20–24, 2006. Proceedings. Berlin: Springer (ISBN 3-540-37432-9/pbk). Lecture Notes in Computer Science 4117, 131-141 (2006).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software