×

Found 74 Documents (Results 1–74)

38th computational complexity conference, CCC 2023, Warwick, UK, July 17–20, 2023. (English) Zbl 1518.68017

LIPIcs – Leibniz International Proceedings in Informatics 264. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik (ISBN 978-3-95977-282-2). xiv, 36 articles, not consecutively paged, electronic only, open access (2023).
MSC:  68-06 68Q25 00B25
PDFBibTeX XMLCite
Full Text: DOI Link

Expander random walks: a Fourier-analytic approach. (English) Zbl 07765276

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). 1643-1655 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Error reduction for weighted PRGs against Read once branching programs. (English) Zbl 07711604

Kabanets, Valentine (ed.), 36th computational complexity conference, CCC 2021, Toronto, Ontario, Canada, virtual conference, July 20–23, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 200, Article 22, 17 p. (2021).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

On hitting-set generators for polynomials that vanish rarely. (English) Zbl 07758309

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 7, 23 p. (2020).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

Near-optimal erasure list-decodable codes. (English) Zbl 07561729

Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 1, 27 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Two-source condensers with low error and small entropy gap via entropy-resilient functions. (English) Zbl 07650110

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 43, 20 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

List decoding with double samplers. (English) Zbl 1435.94155

Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2134-2153 (2019).
MSC:  94B35 68R10 68Q87
PDFBibTeX XMLCite
Full Text: DOI arXiv

A new approach for constructing low-error, two-source extractors. (English) Zbl 1441.68034

Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 3, 19 p. (2018).
MSC:  68P30 68Q87 68R05
PDFBibTeX XMLCite
Full Text: DOI

Probabilistic logarithmic-space algorithms for Laplacian solvers. (English) Zbl 1467.68212

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 41, 20 p. (2017).
MSC:  68W20 05C50 68Q25
PDFBibTeX XMLCite
Full Text: DOI

An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. (English) Zbl 1370.68082

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). 1185-1194 (2017).
PDFBibTeX XMLCite
Full Text: DOI

Explicit, almost optimal, epsilon-balanced codes. (English) Zbl 1378.94079

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). 238-251 (2017).
MSC:  94B05 05C81
PDFBibTeX XMLCite
Full Text: DOI

On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace. (English) Zbl 1440.68332

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

The Benes network is \(q(q-1)/2n\)-almost \(q\)-set-wise independent. (English) Zbl 1360.94500

Raman, Venkatesh (ed.) et al., 34th international conference on foundation of software technology and theoretical computer science, FSTTCS 2014, New Delhi, India, December 15–17, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-77-4). LIPIcs – Leibniz International Proceedings in Informatics 29, 327-338 (2014).
MSC:  94C15 94A60
PDFBibTeX XMLCite
Full Text: DOI

Inverting well conditioned matrices in quantum logspace. (English) Zbl 1293.68129

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). 881-890 (2013).
MSC:  68Q12 65F10 81P68
PDFBibTeX XMLCite
Full Text: DOI

Short seed extractors against quantum storage. (English) Zbl 1304.68053

Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 401-408 (2009).
MSC:  68Q12 81P68 94B35
PDFBibTeX XMLCite
Full Text: DOI

Constructing small-bias sets from algebraic-geometric codes. (English) Zbl 1292.94182

2009 IEEE 50th annual symposium on foundations of computer science – FOCS 2009. Proceedings of the symposium, Atlanta, GA, USA, October 24–27, 2009. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-3850-1; 978-1-4244-5116-6/ebook). 191-197 (2009).
PDFBibTeX XMLCite
Full Text: DOI

A combinatorial construction of almost-Ramanujan graphs using the zig-zag product. (English) Zbl 1231.05224

STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-047-0). 325-334 (2008).
MSC:  05C76
PDFBibTeX XMLCite

Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. (English) Zbl 1302.68220

Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 599-608 (2007).
PDFBibTeX XMLCite

Worst-case to average-case reductions revisited. (English) Zbl 1171.68498

Charikar, Moses (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 10th international workshop, APPROX 2007, and 11th international workshop, RANDOM 2007, Princeton, NJ, USA, August 20–22, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74207-4/pbk). Lecture Notes in Computer Science 4627, 569-583 (2007).
MSC:  68Q25 03D15 68Q17
PDFBibTeX XMLCite
Full Text: DOI

On the error parameter of dispersers. (English) Zbl 1142.68466

Chekuri, Chandra (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 8th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2005, and 9th international workshop on randomization and computation, RANDOM 2005, Berkeley, CA, USA, August 22–24, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28239-4/pbk). Lecture Notes in Computer Science 3624, 294-305 (2005).
MSC:  68R99 05C55
PDFBibTeX XMLCite
Full Text: DOI

Improving the alphabet-size in high noise, almost optimal rate list decodable codes. (English) Zbl 1118.94321

Diekert, Volker (ed.) et al., STACS 2005. 22nd annual symposium on theoretical aspects of computer science, Stuttgart, Germany, February 24–26, 2005. Proceedings. Berlin: Springer (ISBN 3-540-24998-2/pbk). Lecture Notes in Computer Science 3404, 557-568 (2005).
MSC:  94B35
PDFBibTeX XMLCite
Full Text: DOI

Non-interactive timestamping in the bounded storage model. (English) Zbl 1104.94051

Franklin, Matt (ed.), Advances in cryptology – CRYPTO 2004. 24th annual international cryptology conference, Santa Barbara, California, USA, August 15–19, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22668-0/pbk). Lecture Notes in Computer Science 3152, 460-476 (2004).
MSC:  94A62 68M12 68P25
PDFBibTeX XMLCite
Full Text: DOI

Provable unlinkability against traffic analysis. (English) Zbl 1105.94303

Juels, Ari (ed.), Financial cryptography. 8th international conference, FC 2004, Key West, FL, USA, February 9–12, 2004. Revised papers. Berlin: Springer (ISBN 3-540-22420-3/pbk). Lecture Notes in Computer Science 3110, 266-280 (2004).
PDFBibTeX XMLCite
Full Text: DOI

Adiabatic quantum state generation and statistical zero knowledge. (English) Zbl 1192.81048

Proceedings of the thirty-fifth annual ACM symposium on theory of computing (STOC 2003), San Diego, CA, USA,. New York, NY: ACM Press (ISBN 1-58113-674-9). 20-29, electronic only (2003).
MSC:  81P68 68Q05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Extractor codes. (English) Zbl 1323.94179

Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6–8, 2001. New York, NY: ACM Press (ISBN 1-581-13349-9). 193-199 (2001).
PDFBibTeX XMLCite
Full Text: DOI

Loss-less condensers, unbalanced expanders, and extractors. (English) Zbl 1323.68263

Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6–8, 2001. New York, NY: ACM Press (ISBN 1-581-13349-9). 143-152 (2001).
PDFBibTeX XMLCite
Full Text: DOI

Interaction in quantum communication and the complexity of Set Disjointness. (English) Zbl 1323.68287

Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC 2001. Hersonissos, Crete, Greece, July 6–8, 2001. New York, NY: ACM Press (ISBN 1-581-13349-9). 124-133 (2001).
MSC:  68Q12 68Q05 81P45 81P68
PDFBibTeX XMLCite
Full Text: DOI

Quantum bit escrow. (English) Zbl 1296.94074

Proceedings of the thirty-second annual ACM symposium on theory of computing (STOC 2000), Portland, Oregon, USA, May 21–23, 2000. New York, NY: ACM Press (ISBN 1-58113-184-4). 705-714 (2000).
MSC:  94A60 81P94
PDFBibTeX XMLCite
Full Text: DOI arXiv

Normal subgroup reconstruction and quantum computation using group representations. (English) Zbl 1296.68056

Proceedings of the thirty-second annual ACM symposium on theory of computing (STOC 2000), Portland, Oregon, USA, May 21–23, 2000. New York, NY: ACM Press (ISBN 1-58113-184-4). 627-635 (2000).
MSC:  68Q12 20C15 81P68
PDFBibTeX XMLCite
Full Text: DOI

Dense quantum coding and a lower bound for 1-way quantum automata. (English) Zbl 1345.68195

Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 376-383 (1999).
PDFBibTeX XMLCite
Full Text: DOI

Flow control: A new approach for anonymity control in electronic cash systems. (English) Zbl 1046.68525

Franklin, Matthew (ed.), Financial cryptography. 3rd international conference, FC ’99. Anguilla, British West Indies, February 22–25, 1999. Proceedings. Berlin: Springer (ISBN 3-540-66362-2). Lect. Notes Comput. Sci. 1648, 46-61 (1999).
MSC:  68P25 94A60
PDFBibTeX XMLCite

\(SL\subseteq L^{4/3}\). (English) Zbl 0968.68118

STOC ’97. Proceedings of the 29th annual ACM symposium on theory of computing, El Paso, TX, USA, May 4-6, 1997. New York, NY: ACM, Association for Computing Machinery, 230-239 (1999).
MSC:  68R10
PDFBibTeX XMLCite

Almost optimal dispersers. (English) Zbl 1027.68648

STOC ’98. Proceedings of the 30th annual ACM symposium on theory of computing, Dallas, TX, USA, May 23-26, 1998. New York, NY: ACM, Association for Computing Machinery. 196-202 (1998).
MSC:  68R10
PDFBibTeX XMLCite

On extracting randomness from weak random sources. (Extended abstract). (English) Zbl 0924.68210

Proceedings of the 28th annual ACM symposium on the theory of computing (STOC). Philadelphia, PA, USA, May 22–24, 1996. New York, NY: ACM, 276-285 (1996).
MSC:  68U20
PDFBibTeX XMLCite

Symmetric logspace is closed under complement. (English) Zbl 0978.68525

Proceedings of the 27th annual ACM symposium on the theory of computing (STOC). Las Vegas, NV, USA, May 29 - June 1, 1995. New York, NY: ACM, 140-146 (1995).
MSC:  68Q15 68N15
PDFBibTeX XMLCite

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field

Software