Ta-Shma, Amnon (ed.) 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 \textit{A. Ta-Shma} (ed.), 38th computational complexity conference, CCC 2023, Warwick, UK, July 17--20, 2023. Wadern: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik (2023; Zbl 1518.68017) Full Text: DOI Link
Doron, Dean; Ta-Shma, Amnon; Tell, Roei On hitting-set generators for polynomials that vanish rarely. (English) Zbl 07622848 Comput. Complexity 31, No. 2, Paper No. 16, 62 p. (2022). MSC: 68Q87 11T06 PDFBibTeX XMLCite \textit{D. Doron} et al., Comput. Complexity 31, No. 2, Paper No. 16, 62 p. (2022; Zbl 07622848) Full Text: DOI
Ben-Aroya, Avraham; Doron, Dean; Ta-Shma, Amnon An efficient reduction from two-source to nonmalleable extractors: achieving near-logarithmic min-entropy. (English) Zbl 07516619 SIAM J. Comput. 51, No. 2, STOC17-31-STOC17-49 (2022). MSC: 68Q87 05D10 PDFBibTeX XMLCite \textit{A. Ben-Aroya} et al., SIAM J. Comput. 51, No. 2, STOC17--31-STOC17--49 (2022; Zbl 07516619) Full Text: DOI
Cohen, Gil; Peri, Noam; Ta-Shma, Amnon 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 \textit{G. Cohen} et al., in: 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; Zbl 07765276) Full Text: DOI
Cohen, Gil; Doron, Dean; Renard, Oren; Sberlo, Ori; Ta-Shma, Amnon 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 \textit{G. Cohen} et al., LIPIcs -- Leibniz Int. Proc. Inform. 200, Article 22, 17 p. (2021; Zbl 07711604) Full Text: DOI
Dinur, Irit; Harsha, Prahladh; Kaufman, Tali; Navon, Inbal Livni; Ta-Shma, Amnon List-decoding with double samplers. (English) Zbl 1518.94147 SIAM J. Comput. 50, No. 2, 301-349 (2021). MSC: 94B35 05C48 68R10 PDFBibTeX XMLCite \textit{I. Dinur} et al., SIAM J. Comput. 50, No. 2, 301--349 (2021; Zbl 1518.94147) Full Text: DOI
Doron, Dean; Ta-Shma, Amnon; Tell, Roei 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 \textit{D. Doron} et al., LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 7, 23 p. (2020; Zbl 07758309) Full Text: DOI
Ben-Aroya, Avraham; Doron, Dean; Ta-Shma, Amnon 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 \textit{A. Ben-Aroya} et al., LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 1, 27 p. (2020; Zbl 07561729) Full Text: DOI
Ben-Aroya, Avraham; Cohen, Gil; Doron, Dean; Ta-Shma, Amnon 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 \textit{A. Ben-Aroya} et al., LIPIcs -- Leibniz Int. Proc. Inform. 145, Article 43, 20 p. (2019; Zbl 07650110) Full Text: DOI
Aviv, Nir; Ta-Shma, Amnon On the entropy loss and gap of condensers. (English) Zbl 1497.68167 ACM Trans. Comput. Theory 11, No. 3, Article No. 15, 14 p. (2019). MSC: 68P30 PDFBibTeX XMLCite \textit{N. Aviv} and \textit{A. Ta-Shma}, ACM Trans. Comput. Theory 11, No. 3, Article No. 15, 14 p. (2019; Zbl 1497.68167) Full Text: DOI
Dinur, Irit; Harsha, Prahladh; Kaufman, Tali; Navon, Inbal Livni; Shma, Amnon Ta 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 \textit{I. Dinur} et al., in: 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; Zbl 1435.94155) Full Text: DOI arXiv
Ben-Aroya, Avraham; Chattopadhyay, Eshan; Doron, Dean; Li, Xin; Ta-Shma, Amnon 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 \textit{A. Ben-Aroya} et al., LIPIcs -- Leibniz Int. Proc. Inform. 102, Article 3, 19 p. (2018; Zbl 1441.68034) Full Text: DOI
Doron, Dean; Le Gall, François; Ta-Shma, Amnon 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 \textit{D. Doron} et al., LIPIcs -- Leibniz Int. Proc. Inform. 81, Article 41, 20 p. (2017; Zbl 1467.68212) Full Text: DOI
Doron, Dean; Sarid, Amir; Ta-Shma, Amnon On approximating the eigenvalues of stochastic matrices in probabilistic logspace. (English) Zbl 1378.68049 Comput. Complexity 26, No. 2, 393-420 (2017). MSC: 68Q17 65F15 68Q15 68R10 68W20 68W25 PDFBibTeX XMLCite \textit{D. Doron} et al., Comput. Complexity 26, No. 2, 393--420 (2017; Zbl 1378.68049) Full Text: DOI
Ben-Aroya, Avraham; Doron, Dean; Ta-Shma, Amnon 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). MSC: 68P30 05C55 05C80 68Q87 PDFBibTeX XMLCite \textit{A. Ben-Aroya} et al., in: 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). 1185--1194 (2017; Zbl 1370.68082) Full Text: DOI
Ta-Shma, Amnon 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 \textit{A. Ta-Shma}, in: 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). 238--251 (2017; Zbl 1378.94079) Full Text: DOI
Doron, Dean; Ta-Shma, Amnon 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). MSC: 68W25 05C50 15A18 15B51 68Q12 68Q25 PDFBibTeX XMLCite \textit{D. Doron} and \textit{A. Ta-Shma}, Lect. Notes Comput. Sci. 9134, 419--431 (2015; Zbl 1440.68332) Full Text: DOI
Berman, Ron; Fiat, Amos; Gomułkiewicz, Marcin; Klonowski, Marek; Kutyłowski, Mirosław; Levinboim, Tomer; Ta-Shma, Amnon Provable unlinkability against traffic analysis with low message overhead. (English) Zbl 1356.94050 J. Cryptology 28, No. 3, 623-640 (2015). MSC: 94A60 94C99 PDFBibTeX XMLCite \textit{R. Berman} et al., J. Cryptology 28, No. 3, 623--640 (2015; Zbl 1356.94050) Full Text: DOI
Doron, Dean; Ta-Shma, Amnon On the de-randomization of space-bounded approximate counting problems. (English) Zbl 1329.68287 Inf. Process. Lett. 115, No. 10, 750-753 (2015). MSC: 68W25 68Q12 68W20 PDFBibTeX XMLCite \textit{D. Doron} and \textit{A. Ta-Shma}, Inf. Process. Lett. 115, No. 10, 750--753 (2015; Zbl 1329.68287) Full Text: DOI
Gelman, Efraim; Ta-Shma, Amnon 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 \textit{E. Gelman} and \textit{A. Ta-Shma}, LIPIcs -- Leibniz Int. Proc. Inform. 29, 327--338 (2014; Zbl 1360.94500) Full Text: DOI
Ta-Shma, Amnon; Zwick, Uri Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. (English) Zbl 1333.68216 ACM Trans. Algorithms 10, No. 3, Article No. 12, 15 p. (2014). MSC: 68R10 05C40 05C85 68T40 68T42 PDFBibTeX XMLCite \textit{A. Ta-Shma} and \textit{U. Zwick}, ACM Trans. Algorithms 10, No. 3, Article No. 12, 15 p. (2014; Zbl 1333.68216) Full Text: DOI
Ben-Aroya, Avraham; Ta-Shma, Amnon Constructing small-bias sets from algebraic-geometric codes. (English) Zbl 1345.94103 Theory Comput. 9, Paper No. 5, 253-272 (2013). Reviewer: Diego Ruano (Aalborg) MSC: 94B27 12Y05 PDFBibTeX XMLCite \textit{A. Ben-Aroya} and \textit{A. Ta-Shma}, Theory Comput. 9, Paper No. 5, 253--272 (2013; Zbl 1345.94103) Full Text: DOI
Ta-Shma, Amnon 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 \textit{A. Ta-Shma}, in: 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). 881--890 (2013; Zbl 1293.68129) Full Text: DOI
Ben-Aroya, Avraham; Ta-Shma, Amnon Better short-seed quantum-proof extractors. (English) Zbl 1288.68067 Theor. Comput. Sci. 419, 17-25 (2012). MSC: 68Q12 81P68 94A17 PDFBibTeX XMLCite \textit{A. Ben-Aroya} and \textit{A. Ta-Shma}, Theor. Comput. Sci. 419, 17--25 (2012; Zbl 1288.68067) Full Text: DOI arXiv
Ben-Aroya, Avraham; Ta-Shma, Amnon Approximate quantum error correction for correlated noise. (English) Zbl 1365.81037 IEEE Trans. Inf. Theory 57, No. 6, 3982-3988 (2011). MSC: 81P70 94B05 PDFBibTeX XMLCite \textit{A. Ben-Aroya} and \textit{A. Ta-Shma}, IEEE Trans. Inf. Theory 57, No. 6, 3982--3988 (2011; Zbl 1365.81037) Full Text: DOI arXiv
Ta-Shma, Amnon Short seed extractors against quantum storage. (English) Zbl 1253.68135 SIAM J. Comput. 40, No. 3, 664-677 (2011). MSC: 68Q12 94A60 PDFBibTeX XMLCite \textit{A. Ta-Shma}, SIAM J. Comput. 40, No. 3, 664--677 (2011; Zbl 1253.68135) Full Text: DOI arXiv
Ben-Aroya, Avraham; Ta-Shma, Amnon A combinatorial construction of almost-Ramanujan graphs using the zig-zag product. (English) Zbl 1222.05147 SIAM J. Comput. 40, No. 2, 267-290 (2011). MSC: 05C50 PDFBibTeX XMLCite \textit{A. Ben-Aroya} and \textit{A. Ta-Shma}, SIAM J. Comput. 40, No. 2, 267--290 (2011; Zbl 1222.05147) Full Text: DOI Backlinks: MO
Ben-Aroya, Avraham; Schwartz, Oded; Ta-Shma, Amnon Quantum expanders: motivation and construction. (English) Zbl 1213.81052 Theory Comput. 6, Paper No. 3, 47-79 (2010). MSC: 81P68 68Q12 68Q17 PDFBibTeX XMLCite \textit{A. Ben-Aroya} et al., Theory Comput. 6, Paper No. 3, 47--79 (2010; Zbl 1213.81052) Full Text: DOI
Ben-Aroya, Avraham; Ta-Shma, Amnon On the complexity of approximating the diamond norm. (English) Zbl 1183.81035 Quantum Inf. Comput. 10, No. 1-2, 77-86 (2010). MSC: 81P68 68Q15 PDFBibTeX XMLCite \textit{A. Ben-Aroya} and \textit{A. Ta-Shma}, Quantum Inf. Comput. 10, No. 1--2, 77--86 (2010; Zbl 1183.81035) Full Text: arXiv
Ta-Shma, Amnon 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 \textit{A. Ta-Shma}, in: 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). 401--408 (2009; Zbl 1304.68053) Full Text: DOI
Ben-Aroya, Avraham; Ta-Shma, Amnon 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). MSC: 94B27 68Q87 68R05 14G50 PDFBibTeX XMLCite \textit{A. Ben-Aroya} and \textit{A. Ta-Shma}, in: 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. 191--197 (2009; Zbl 1292.94182) Full Text: DOI
Moran, Tal; Shaltiel, Ronen; Ta-Shma, Amnon Non-interactive timestamping in the bounded-storage model. (English) Zbl 1159.94368 J. Cryptology 22, No. 2, 189-226 (2009). MSC: 94A60 94A62 PDFBibTeX XMLCite \textit{T. Moran} et al., J. Cryptology 22, No. 2, 189--226 (2009; Zbl 1159.94368) Full Text: DOI
Ben-Aroya, Avraham; Ta-Shma, Amnon 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 \textit{A. Ben-Aroya} and \textit{A. Ta-Shma}, in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17--20, 2008. New York, NY: Association for Computing Machinery (ACM). 325--334 (2008; Zbl 1231.05224)
Ta-Shma, Amnon; Zwick, Uri 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). MSC: 68R10 05C40 05C85 68T40 PDFBibTeX XMLCite \textit{A. Ta-Shma} and \textit{U. Zwick}, in: 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). 599--608 (2007; Zbl 1302.68220)
Haviv, Ishay; Regev, Oded; Ta-Shma, Amnon On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. (English) Zbl 1213.68311 Theory Comput. 3, Paper No. 3, 45-60 (2007). MSC: 68Q17 03D15 68Q15 PDFBibTeX XMLCite \textit{I. Haviv} et al., Theory Comput. 3, Paper No. 3, 45--60 (2007; Zbl 1213.68311) Full Text: DOI arXiv
Gutfreund, Dan; Ta-Shma, Amnon 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 \textit{D. Gutfreund} and \textit{A. Ta-Shma}, Lect. Notes Comput. Sci. 4627, 569--583 (2007; Zbl 1171.68498) Full Text: DOI
Klauck, Hartmut; Nayak, Ashwin; Ta-Shma, Amnon; Zuckerman, David Interaction in quantum communication. (English) Zbl 1323.94066 IEEE Trans. Inf. Theory 53, No. 6, 1970-1982 (2007). MSC: 94A24 81P45 PDFBibTeX XMLCite \textit{H. Klauck} et al., IEEE Trans. Inf. Theory 53, No. 6, 1970--1982 (2007; Zbl 1323.94066) Full Text: DOI arXiv
Aharonov, Dorit; Ta-Shma, Amnon Adiabatic quantum state generation. (English) Zbl 1134.81008 SIAM J. Comput. 37, No. 1, 47-82 (2007). MSC: 81P68 70H11 68Q99 68Q05 PDFBibTeX XMLCite \textit{D. Aharonov} and \textit{A. Ta-Shma}, SIAM J. Comput. 37, No. 1, 47--82 (2007; Zbl 1134.81008) Full Text: DOI Link
Gutfreund, Dan; Shaltiel, Ronen; Ta-Shma, Amnon If NP languages are hard on the worst-case, then it is easy to find their hard instances. (English) Zbl 1133.68352 Comput. Complexity 16, No. 4, 412-441 (2007). MSC: 68Q17 68Q10 68Q15 94A60 PDFBibTeX XMLCite \textit{D. Gutfreund} et al., Comput. Complexity 16, No. 4, 412--441 (2007; Zbl 1133.68352) Full Text: DOI
Rapaport, Alex; Ta-Shma, Amnon On the power of quantum, one round, two prover interactive proof systems. (English) Zbl 1137.81008 Quantum Inf. Process. 6, No. 6, 445-459 (2007). MSC: 81P68 91A99 PDFBibTeX XMLCite \textit{A. Rapaport} and \textit{A. Ta-Shma}, Quantum Inf. Process. 6, No. 6, 445--459 (2007; Zbl 1137.81008) Full Text: DOI arXiv
Ta-Shma, Amnon; Umans, Christopher; Zuckerman, David Lossless condensers, unbalanced expanders, and extractors. (English) Zbl 1164.68004 Combinatorica 27, No. 2, 213-240 (2007). Reviewer: Heribert Vollmer (Hannover) MSC: 68Q01 68Q10 68R10 PDFBibTeX XMLCite \textit{A. Ta-Shma} et al., Combinatorica 27, No. 2, 213--240 (2007; Zbl 1164.68004) Full Text: DOI
Rom, Eran; Ta-Shma, Amnon Improving the alphabet-size in expander-based code constructions. (English) Zbl 1309.94163 IEEE Trans. Inf. Theory 52, No. 8, 3695-3700 (2006). MSC: 94B05 94B35 PDFBibTeX XMLCite \textit{E. Rom} and \textit{A. Ta-Shma}, IEEE Trans. Inf. Theory 52, No. 8, 3695--3700 (2006; Zbl 1309.94163) Full Text: DOI
Ta-Shma, Amnon; Zuckerman, David; Safra, Shmuel Extractors from Reed-Muller codes. (English) Zbl 1094.68036 J. Comput. Syst. Sci. 72, No. 5, 786-812 (2006). MSC: 94B27 68W99 PDFBibTeX XMLCite \textit{A. Ta-Shma} et al., J. Comput. Syst. Sci. 72, No. 5, 786--812 (2006; Zbl 1094.68036) Full Text: DOI
Gradwohl, Ronen; Kindler, Guy; Reingold, Omer; Ta-Shma, Amnon 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 \textit{R. Gradwohl} et al., Lect. Notes Comput. Sci. 3624, 294--305 (2005; Zbl 1142.68466) Full Text: DOI
Rom, Eran; Ta-Shma, Amnon 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 \textit{E. Rom} and \textit{A. Ta-Shma}, Lect. Notes Comput. Sci. 3404, 557--568 (2005; Zbl 1118.94321) Full Text: DOI
Ta-Shma, Amnon; Zuckerman, David Extractor codes. (English) Zbl 1298.94148 IEEE Trans. Inf. Theory 50, No. 12, 3015-3025 (2004). MSC: 94B60 94A40 PDFBibTeX XMLCite \textit{A. Ta-Shma} and \textit{D. Zuckerman}, IEEE Trans. Inf. Theory 50, No. 12, 3015--3025 (2004; Zbl 1298.94148) Full Text: DOI
Moran, Tal; Shaltiel, Ronen; Ta-Shma, Amnon 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 \textit{T. Moran} et al., Lect. Notes Comput. Sci. 3152, 460--476 (2004; Zbl 1104.94051) Full Text: DOI
Berman, Ron; Fiat, Amos; Ta-Shma, Amnon 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). MSC: 94A60 68M10 68M12 94A15 PDFBibTeX XMLCite \textit{R. Berman} et al., Lect. Notes Comput. Sci. 3110, 266--280 (2004; Zbl 1105.94303) Full Text: DOI
Aharonov, Dorit; Ta-Shma, Amnon 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 \textit{D. Aharonov} and \textit{A. Ta-Shma}, in: Proceedings of the thirty-fifth annual ACM symposium on theory of computing, STOC 2003. San Diego, CA, USA. New York, NY: ACM Press. 20--29 (2003; Zbl 1192.81048) Full Text: DOI arXiv
Gutfreund, Dan; Shaltiel, Ronen; Ta-Shma, Amnon Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. (English) Zbl 1085.68055 Comput. Complexity 12, No. 3-4, 85-130 (2003). MSC: 68Q15 PDFBibTeX XMLCite \textit{D. Gutfreund} et al., Comput. Complexity 12, No. 3--4, 85--130 (2003; Zbl 1085.68055) Full Text: DOI
Ambainis, Andris; Schulman, Leonard J.; Ta-Shma, Amnon; Vazirani, Umesh; Wigderson, Avi The quantum communication complexity of sampling. (English) Zbl 1041.68002 SIAM J. Comput. 32, No. 6, 1570-1585 (2003). MSC: 68M10 68Q10 68R05 PDFBibTeX XMLCite \textit{A. Ambainis} et al., SIAM J. Comput. 32, No. 6, 1570--1585 (2003; Zbl 1041.68002) Full Text: DOI
Hallgren, Sean; Russell, Alexander; Ta-Shma, Amnon The hidden subgroup problem and quantum computation using group representations. (English) Zbl 1029.81015 SIAM J. Comput. 32, No. 4, 916-934 (2003). MSC: 81P68 68Q17 PDFBibTeX XMLCite \textit{S. Hallgren} et al., SIAM J. Comput. 32, No. 4, 916--934 (2003; Zbl 1029.81015) Full Text: DOI
Ambainis, Andris; Nayak, Ashwin; Ta-Shma, Amnon; Vazirani, Umesh Dense quantum coding and quantum finite automata. (English) Zbl 1326.68133 J. ACM 49, No. 4, 496-511 (2002). MSC: 68Q05 68Q45 81P45 81P70 81P68 PDFBibTeX XMLCite \textit{A. Ambainis} et al., J. ACM 49, No. 4, 496--511 (2002; Zbl 1326.68133) Full Text: DOI
Ta-Shma, Amnon Storing information with extractors. (English) Zbl 1051.68049 Inf. Process. Lett. 83, No. 5, 267-274 (2002). MSC: 68P05 PDFBibTeX XMLCite \textit{A. Ta-Shma}, Inf. Process. Lett. 83, No. 5, 267--274 (2002; Zbl 1051.68049) Full Text: DOI
Ta-Shma, Amnon Almost optimal dispersers. (English) Zbl 0994.68068 Combinatorica 22, No. 1, 123-145 (2002). MSC: 68Q01 68R10 PDFBibTeX XMLCite \textit{A. Ta-Shma}, Combinatorica 22, No. 1, 123--145 (2002; Zbl 0994.68068) Full Text: DOI
Ta-Shma, Amnon; Zucherman, David 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). MSC: 94B60 68Q25 68R10 94B35 PDFBibTeX XMLCite \textit{A. Ta-Shma} and \textit{D. Zucherman}, in: 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. 193--199 (2001; Zbl 1323.94179) Full Text: DOI
Ta-Shma, Amnon; Umans, Christopher; Zuckerman, David 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). MSC: 68P30 68Q17 68W20 94A17 PDFBibTeX XMLCite \textit{A. Ta-Shma} et al., in: 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. 143--152 (2001; Zbl 1323.68263) Full Text: DOI
Klauck, Hartmut; Nayak, Ashwin; Ta-Shma, Amnon; Zuckerman, David 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 \textit{H. Klauck} et al., in: 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. 124--133 (2001; Zbl 1323.68287) Full Text: DOI
Sander, Tomas; Ta-Shma, Amnon; Yung, Moti Blind, auditable membership proofs. (English) Zbl 0999.94547 Frankel, Yair (ed.), Financial cryptography. 4th international conference, FC 2000, Anguilla, British West Indies, February 20-24, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1962, 53-71 (2001). MSC: 94A62 68W40 PDFBibTeX XMLCite \textit{T. Sander} et al., Lect. Notes Comput. Sci. 1962, 53--71 (2001; Zbl 0999.94547)
Aharonov, Dorit; Ta-Shma, Amnon; Vazirani, Umesh V.; Yao, Andrew C. 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 \textit{D. Aharonov} et al., in: 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. 705--714 (2000; Zbl 1296.94074) Full Text: DOI arXiv
Hallgren, Sean; Russell, Alexander; Ta-Shma, Amnon 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 \textit{S. Hallgren} et al., in: 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. 627--635 (2000; Zbl 1296.68056) Full Text: DOI
Armoni, Roy; Ta-Shma, Amnon; Widgerson, Avi; Zhou, Shiyu An \(O(\log(n)^{4/3})\) space algorithm for \((s, t)\) connectivity in undirected graphs. (English) Zbl 1133.68341 J. ACM 47, No. 2, 294-311 (2000). MSC: 68Q05 68Q15 68R10 05C85 PDFBibTeX XMLCite \textit{R. Armoni} et al., J. ACM 47, No. 2, 294--311 (2000; Zbl 1133.68341) Full Text: DOI
Radhakrishnan, Jaikumar; Ta-Shma, Amnon Bounds for dispersers, extractors, and depth-two superconcentrators. (English) Zbl 1023.94025 SIAM J. Discrete Math. 13, No. 1, 2-24 (2000). MSC: 94C15 05C90 05C35 94A17 PDFBibTeX XMLCite \textit{J. Radhakrishnan} and \textit{A. Ta-Shma}, SIAM J. Discrete Math. 13, No. 1, 2--24 (2000; Zbl 1023.94025) Full Text: DOI
Ambainis, Andris; Nayak, Ashwin; Ta-Shma, Ammon; Vazirani, Umesh 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). MSC: 68Q45 68Q12 81P68 81P70 PDFBibTeX XMLCite \textit{A. Ambainis} et al., in: 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. 376--383 (1999; Zbl 1345.68195) Full Text: DOI
Sander, Tomas; Ta-Shma, Amnon 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 \textit{T. Sander} and \textit{A. Ta-Shma}, Lect. Notes Comput. Sci. 1648, 46--61 (1999; Zbl 1046.68525)
Armoni, Roy; Ta-Shma, Amnon; Wigderson, Avi; Zhou, Shiyu \(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 \textit{R. Armoni} et al., in: Proceedings of the 29th annual ACM symposium on theory of computing, STOC '97. El Paso, TX, USA, May 4--6, 1997. New York, NY: ACM, Association for Computing Machinery. 230--239 (1999; Zbl 0968.68118)
Sander, Tomas; Ta-Shma, Amnon Auditable, anonymous electronic cash. (Extended abstract). (English) Zbl 0949.68530 Wiener, Michael (ed.), Advances in cryptology - CRYPTO ’99. 19th annual international cryptology conference Santa Barbara, CA, USA, August 15-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1666, 555-572 (1999). MSC: 68P25 PDFBibTeX XMLCite \textit{T. Sander} and \textit{A. Ta-Shma}, Lect. Notes Comput. Sci. 1666, 555--572 (1999; Zbl 0949.68530)
Sander, Tomas; Ta-Shma, Amnon Flow control: A new approach for anonymity control in electronic cash systems. (English) Zbl 0979.68536 Franklin, Matthew (ed.), Financial cryptography. 3rd international conference, FC ’99. Anguilla, British West Indies, February 22-25, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1648, 46-61 (1999). MSC: 68P25 PDFBibTeX XMLCite \textit{T. Sander} and \textit{A. Ta-Shma}, Lect. Notes Comput. Sci. 1648, 46--61 (1999; Zbl 0979.68536)
Nisan, Noam; Ta-Shma, Amnon Extracting randomness: A survey and new constructions. (English) Zbl 0943.68190 J. Comput. Syst. Sci. 58, No. 1, 148-173 (1999). MSC: 68W20 PDFBibTeX XMLCite \textit{N. Nisan} and \textit{A. Ta-Shma}, J. Comput. Syst. Sci. 58, No. 1, 148--173 (1999; Zbl 0943.68190) Full Text: DOI
Ta-Shma, Amnon 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 \textit{A. Ta-Shma}, in: Proceedings of the 30th annual ACM symposium on theory of computing, STOC '98. Dallas, TX, USA, May 23--26, 1998. New York, NY: ACM, Association for Computing Machinery. 196--202 (1998; Zbl 1027.68648)
Ta-Shma, Amnon A note on PCP vs. MIP. (English) Zbl 0875.68428 Inf. Process. Lett. 58, No. 3, 135-140 (1996). MSC: 68Q15 68W10 PDFBibTeX XMLCite \textit{A. Ta-Shma}, Inf. Process. Lett. 58, No. 3, 135--140 (1996; Zbl 0875.68428) Full Text: DOI
Ta-Shma, Amnon 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 \textit{A. Ta-Shma}, in: Proceedings of the 28th annual ACM symposium on the theory of computing, STOC '96. Philadelphia, PA, USA, May 22--24, 1996. New York, NY: ACM. 276--285 (1996; Zbl 0924.68210)
Nisan, Noam; Ta-Shma, Amnon Symmetric Logspace is closed under complement. (English) Zbl 0924.68039 Chic. J. Theor. Comput. Sci. 1995, Article No. 1 (1995). MSC: 68N17 68Q99 PDFBibTeX XMLCite \textit{N. Nisan} and \textit{A. Ta-Shma}, Chic. J. Theor. Comput. Sci. 1995, Article No. 1 (1995; Zbl 0924.68039) Full Text: DOI
Nisan, Noam; Ta-Shma, Amnon 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 \textit{N. Nisan} and \textit{A. Ta-Shma}, in: Proceedings of the 27th annual ACM symposium on the theory of computing, STOC '95. Las Vegas, NV, USA, May 29 -- June 1, 1995. New York, NY: ACM. 140--146 (1995; Zbl 0978.68525)