×

Found 82 Documents (Results 1–82)

Approximating iterated multiplication of stochastic matrices in small space. (English) Zbl 07844570

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 35-45 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Near-optimal derandomization of medium-width branching programs. (English) Zbl 07844569

Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 23-34 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Pseudodistributions that beat all pseudorandom generators (Extended Abstract). (English) Zbl 07711615

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 33, 15 p. (2021).
MSC:  68Q25
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

Quantum logarithmic space and post-selection. (English) Zbl 07701530

Hsieh, Min-Hsiu (ed.), 16th conference on the theory of quantum computation, communication and cryptography, virtual conference, TQC 2021, July 5–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 197, Article 10, 17 p. (2021).
MSC:  81P68 81P94
PDFBibTeX XMLCite
Full Text: DOI arXiv

Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs. (English) Zbl 07670447

Chen, Chi-Yeh (ed.) et al., Computing and combinatorics. 27th international conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13025, 3-12 (2021).
MSC:  68Rxx
PDFBibTeX XMLCite
Full Text: DOI

Optimal error pseudodistributions for Read-once branching programs. (English) Zbl 07561753

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 25, 27 p. (2020).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Pseudorandom generators for width-3 branching programs. (English) Zbl 1433.68604

Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 626-637 (2019).
MSC:  68W20 68P05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Improved pseudorandomness for unordered branching programs through local monotonicity. (English) Zbl 1427.68058

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 363-375 (2018).
MSC:  68P05 68Q87
PDFBibTeX XMLCite
Full Text: DOI

Hitting sets with near-optimal error for read-once branching programs. (English) Zbl 1427.68095

Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 353-362 (2018).
MSC:  68Q15 68W20
PDFBibTeX XMLCite
Full Text: DOI

Generalizations of checking stack automata: characterizations and hierarchies. (English) Zbl 1517.68198

Hoshi, Mizuho (ed.) et al., Developments in language theory. 22nd international conference, DLT 2018, Tokyo, Japan, September 10–14, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11088, 416-428 (2018).
MSC:  68Q45 68Q04
PDFBibTeX XMLCite
Full Text: DOI arXiv

A note on the advice complexity of multipass randomized logspace. (English) Zbl 1398.68178

Faliszewski, Piotr (ed.) et al., 41st international symposium on mathematical foundations of computer science, MFCS 2016, Kraków, Poland, August 22–26, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-016-3). LIPIcs – Leibniz International Proceedings in Informatics 58, Article 31, 7 p. (2016).
MSC:  68Q15 68Q05 68Q10
PDFBibTeX XMLCite
Full Text: DOI

Space-efficient error reduction for unitary quantum computations. (English) Zbl 1388.68067

Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 14, 14 p. (2016).
MSC:  68Q12 81P68
PDFBibTeX XMLCite
Full Text: DOI arXiv

Space complexity of the directed reachability problem over surface-embedded graphs. (English) Zbl 1345.68149

Agrawal, Manindra (ed.) et al., Perspectives in computational complexity. The Somenath Biswas anniversary volume. Selected papers based on the presentations at the workshop, Kanpur, India, Summer 2012. Cham: Birkhäuser/Springer (ISBN 978-3-319-05445-2/hbk; 978-3-319-05446-9/ebook). Progress in Computer Science and Applied Logic 26, 37-49 (2014).
MSC:  68Q15 05C85 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Space-bounded communication complexity. (English) Zbl 1360.68457

Proceedings of the 4th conference on innovations in theoretical computer science, ITCS’13, Berkeley, CA, USA, January 9–12, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1859-4). 159-172 (2013).
MSC:  68Q05 68Q10 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Random walks on some basic classes of digraphs. (English) Zbl 1405.68136

Liu, Zhiming (ed.) et al., Theoretical aspects of computing – ICTAC 2013. 10th international colloquium, Shanghai, China, September 4–6, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-39717-2/pbk). Lecture Notes in Computer Science 8049, 122-140 (2013).
PDFBibTeX XMLCite
Full Text: DOI

Higher-order functional reactive programming in bounded space. (English) Zbl 1321.68171

Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’12, Philadelphia, PA, USA, January 22–28, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1083-3). 45-58 (2012).
PDFBibTeX XMLCite
Full Text: DOI

Three XOR-lemmas – an exposition. (English) Zbl 1343.68112

Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 248-272 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Pseudorandom walks on regular digraphs and the RL vs. L problem. (English) Zbl 1301.05317

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). 457-466 (2006).
MSC:  05C81 05C85 68Q25
PDFBibTeX XMLCite
Full Text: DOI

A note on one-pebble two-dimensional Turing machines. (English) Zbl 1173.68519

Del Lungo, Alberto (ed.) et al., 9th international workshop on combinatorial image analysis. Papers from the workshop, Palermo, Italy, May 14–16, 2003. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 12, 360-371 (2003).
MSC:  68Q05
PDFBibTeX XMLCite
Full Text: DOI

The complexity of space bounded interactive proof systems. (English) Zbl 0820.68047

Ambos-Spies, Klaus (ed.) et al., Complexity theory. Current research. Proceedings of the workshop on structure and complexity held at the Dagstuhl International Conference and Research Center, Wadern, Germany, February 2-8, 1992. Cambridge: Cambridge University Press. 147-189 (1993).
PDFBibTeX XMLCite

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field