×

Found 683 Documents (Results 1–100)

Kolmogorov width of discrete linear spaces: an approach to matrix rigidity. (English) Zbl 1388.68135

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, 347-364 (2015).
PDFBibTeX XMLCite
Full Text: DOI

An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets. (English) Zbl 1378.94013

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, 42-57 (2015).
MSC:  94A17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Strong locally testable codes with relaxed local decoders. (English) Zbl 1378.94083

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, 1-41 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Sylvester-Gallai for arrangements of subspaces. (English) Zbl 1382.52021

Arge, Lars (ed.) et al., 31st international symposium on computational geometry, SoCG’15, Eindhoven, Netherlands, June 22–25, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-83-5). LIPIcs – Leibniz International Proceedings in Informatics 34, 29-43 (2015).
MSC:  52C35 15A04
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithmic regularity for polynomials and applications. (English) Zbl 1372.12007

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1870-1889 (2015).
MSC:  12Y05 12E05 11B30 68R05 94B25
PDFBibTeX XMLCite
Full Text: DOI arXiv

LP/SDP hierarchy lower bounds for decoding random LDPC codes. (English) Zbl 1371.94676

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1326-1342 (2015).
MSC:  94B05 94B35 94B65
PDFBibTeX XMLCite
Full Text: DOI arXiv

Limitations on testable affine-invariant codes in the high-rate regime. (English) Zbl 1371.94677

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1312-1325 (2015).
MSC:  94B05
PDFBibTeX XMLCite
Full Text: DOI Link

Deletion codes in the high-noise and high-rate regimes. (English) Zbl 1407.94191

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. LIPIcs – Leibniz Int. Proc. Inform. 40, 867-880 (2015).
MSC:  94B60
PDFBibTeX XMLCite
Full Text: DOI

Dimension expanders via rank condensers. (English) Zbl 1375.68086

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, 800-814 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deciding orthogonality in construction-A lattices. (English) Zbl 1430.94103

Harsha, Prahladh (ed.) et al., 35th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2015, Bangalore, India, December 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 45, 151-162 (2015).
MSC:  94B60 68W40 15B36
PDFBibTeX XMLCite
Full Text: DOI arXiv

Implementing unitary 2-designs using random diagonal-unitary matrices. (English) Zbl 1421.81028

Beigi, Salman (ed.) et al., 10th conference on the theory of quantum computation, communication and cryptography, TQC’15, Brussels, Belgium, May 20–22, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 44, 191-205 (2015).
MSC:  81P70 81P68 94B25
PDFBibTeX XMLCite
Full Text: DOI

It’ll probably work out: improved list-decoding through random operations. (English) Zbl 1364.94727

Proceedings of the 6th conference on innovations in theoretical computer science, ITCS’15, Rehovot, Israel, January 11–13, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3333-7). 287-296 (2015).
MSC:  94B35
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deterministic rateless codes for BSC. (English) Zbl 1364.94268

Proceedings of the 6th conference on innovations in theoretical computer science, ITCS’15, Rehovot, Israel, January 11–13, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3333-7). 31-40 (2015).
MSC:  94A24 94A40 94B05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Serial

all top 3

Main Field

Biographic Reference