Amnon Ta-Shma

2024

The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced

Ta-Shma, A. & Zadicario, R., Sep 2024, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024. Kumar, A. & Ron-Zewi, N. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 31. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 317).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2023

Approximating Iterated Multiplication of Stochastic Matrices in Small Space

Cohen, G., Doron, D., Sberlo, O. & Ta-Shma, A., 2 Jun 2023, STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha, B. & Servedio, R. A. (eds.). Association for Computing Machinery, p. 35-45 11 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

4 Scopus citations

HDX Condensers

Cohen, I., Roth, R. & Ta-Shma, A., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 1649-1664 16 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

2022

Expander Random Walks: The General Case and Limitations

Cohen, G., Minzer, D., Peleg, S., Potechin, A. & Ta-Shma, A., 1 Jul 2022, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Bojanczyk, M., Merelli, E. & Woodruff, D. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 43. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 229).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

Improved Local Testing for Multiplicity Codes

Karliner, D. & Ta-Shma, A., 1 Sep 2022, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022. Chakrabarti, A. & Swamy, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 11. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 245).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

The Plane Test Is a Local Tester for Multiplicity Codes

Karliner, D., Salama, R. & Ta-Shma, A., 1 Jul 2022, 37th Computational Complexity Conference, CCC 2022. Lovett, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 14. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 234).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Unbalanced Expanders from Multiplicity Codes

Kalev, I. & Ta-Shma, A., 1 Sep 2022, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022. Chakrabarti, A. & Swamy, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 12. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 245).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

2021

Error reduction for weighted PRGs against read once branching programs

Cohen, G., Doron, D., Renard, O., Sberlo, O. & Ta-Shma, A., 1 Jul 2021, 36th Computational Complexity Conference, CCC 2021. Kabanets, V. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 22. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 200).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Scopus citations

Expander random walks: A Fourier-analytic approach

Cohen, G., Peri, N. & Ta-Shma, A., 15 Jun 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 1643-1655 13 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

2020

Near-optimal erasure list-decodable codes

Ben-Aroya, A., Doron, D. & Ta-Shma, A., 1 Jul 2020, 35th Computational Complexity Conference, CCC 2020. Saraf, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 1. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 169).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

On hitting-set generators for polynomials that vanish rarely

Doron, D., Ta-Shma, A. & Tell, R., 1 Aug 2020, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020. Byrka, J. & Meka, R. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, APPROX7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 176).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

2019

Two-source condensers with low error and small entropy gap via entropy-resilient functions

Ben-Aroya, A., Cohen, G., Doron, D. & Ta-Shma, A., Sep 2019, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019. Achlioptas, D. & Vegh, L. A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 43. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 145).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

2018

A new approach for constructing low-error, two-source extractors

Ben-Aroya, A., Chattopadhyay, E., Doron, D., Li, X. & Ta-Shma, A., 1 Jun 2018, 33rd Computational Complexity Conference, CCC 2018. Servedio, R. A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 19 p. 3. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 102).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

2017

An efficient reduction from two-source to non-malleable extractors: Achieving near-logarithmic min-entropy

Ben-Aroya, A., Doron, D. & Ta-Shma, A., 19 Jun 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 1185-1194 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

16 Scopus citations

Explicit, almost optimal, epsilon-balanced codes

Ta-Shma, A., 19 Jun 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). Association for Computing Machinery, p. 238-251 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

65 Scopus citations

Probabilistic logarithmic-space algorithms for laplacian solvers

Doron, D., Le Gall, F. & Ta-Shma, A., 1 Aug 2017, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017. Rolim, J. D. P., Jansen, K., Williamson, D. P. & Vempala, S. S. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 41. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 81).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

2015

On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace

Doron, D. & Ta-Shma, A., 2015, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings. Halldorsson, M. M., Kobayashi, N., Speckmann, B. & Iwama, K. (eds.). Springer Verlag, p. 419-431 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9134).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

2014

The benes network is q(q-1)/2n-almost q-set-wise independent

Gelman, E. & Ta-Shma, A., 1 Dec 2014, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014. Raman, V. & Suresh, S. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 327-338 12 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 29).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

2013

Inverting well conditioned matrices in quantum logspace

Ta-Shma, A., 2013, STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing. p. 881-890 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

29 Scopus citations

2012

A new implementation of a dual (paper and cryptographic) voting system

Ben-Nun, J., Farhi, N., Llewellyn, M., Riva, B., Rosen, A., Ta-Shma, A. & Wikström, D., 2012, 5th International Conference on Electronic Voting 2012, EVOTE 2012 - Proceedings. Gesellschaft fur Informatik (GI), p. 315-329 15 p. (Lecture Notes in Informatics (LNI), Proceedings - Series of the Gesellschaft fur Informatik (GI); vol. P-205).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

13 Scopus citations

Better condensers and new extractors from parvaresh-vardy codes

Ta-Shma, A. & Umans, C., 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. p. 309-315 7 p. 6243407. (Proceedings of the Annual IEEE Conference on Computational Complexity).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

14 Scopus citations

2010

Local list-decoding with a constant number of queries

Ben-Aroya, A., Efremenko, K. & Ta-Shma, A., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 715-722 8 p. 5671342. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

20 Scopus citations

2009

Constructing small-bias sets from algebraic-geometric codes

Ben-Aroya, A. & Ta-Shma, A., 2009, Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. p. 191-197 7 p. 5438632. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

21 Scopus citations

Short seed extractors against quantum storage

Ta-Shma, A., 2009, STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing. p. 401-408 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

11 Scopus citations

2008

A combinatorial construction of almost-Ramanujan graphs using the zig-zag product

Ben-Aroya, A. & Ta-Shma, A., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 325-334 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

14 Scopus citations

Quantum expanders: Motivation and constructions

Ben-Aroya, A., Schwartz, O. & Ta-Shma, A., 2008, Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008. p. 292-303 12 p. 4558831. (Proceedings of the Annual IEEE Conference on Computational Complexity).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

7 Scopus citations

2007

Deterministic rendezvous, treasure hunts and strongly universal exploration sequences

Ta-Shma, A. & Zwick, U., 2007, Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007. Association for Computing Machinery, p. 599-608 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 07-09-January-2007).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

56 Scopus citations

Worst-case to average-case reductions revisited

Gutfreund, D. & Ta-Shma, A., 2007, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings. Springer Verlag, p. 569-583 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4627 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

14 Scopus citations

2006

Better lossless condensers through derandomized curve samplers

Ta-Shma, A. & Umans, C., 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006. p. 177-186 10 p. 4031354. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

5 Scopus citations

2005

If NP languages are hard on the worst-case then it is easy to find their hard instances

Gutfreund, D., Shaltiel, R. & Ta-Shma, A., 2005, Proceedings of the 20th Annual IEEE Conference on Computational Complexity. p. 243-257 15 p. (Proceedings of the Annual IEEE Conference on Computational Complexity).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Scopus citations

2001

Blind, auditable membership proofs

Sander, T., Ta-Shma, A. & Yung, M., 2001, Financial Cryptography - 4th International Conference, FC 2000, Proceedings. Frankel, Y. (ed.). Springer Verlag, p. 53-71 19 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1962).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

21 Scopus citations

2000

Normal subgroup reconstruction and quantum computation using group representations

Hallgren, S., Russell, A. & Ta-Shma, A., 2000, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000. p. 627-635 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

66 Scopus citations

Quantum bit escrow

Aharonov, D., Ta-Shma, A., Vazirani, U. V. & Yao, A. C., 2000, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000. p. 705-714 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

94 Scopus citations

1999

Auditable, anonymous electronic cash

Sander, T. & Ta-Shma, A., 1999, Advances in Cryptology – CRYPTO 1999 - 19th Annual International Cryptology Conference, Proceedings. Wiener, M. (ed.). Springer Verlag, p. 555-572 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1666).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Open Access

48 Scopus citations

Flow control: A new approach for anonymity control in electronic cash systems

Sander, T. & Ta-Shma, A., 1999, Financial Cryptography - 3rd International Conference, FC 1999, Proceedings. Franklin, M. (ed.). Springer Verlag, p. 46-61 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1648).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

13 Scopus citations

On anonymous electronic cash and crime

Sander, T. & Ta-Shma, A., 1999, Information Security - 2nd International Workshop, ISW 1999, Proceedings. Mambo, M. & Zheng, Y. (eds.). Springer Verlag, p. 202-206 5 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 1729).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

1997

Tight bounds for depth-two superconcentrators

Radhakrishnan, J. & Ta-Shma, A., 1997, Annual Symposium on Foundations of Computer Science - Proceedings. IEEE Comp Soc, p. 585-594 10 p.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

25 Scopus citations

1996

On extracting randomness from weak random sources

Ta-Shma, A., 1 Jul 1996, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996. Association for Computing Machinery, p. 276-285 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F129452).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

58 Scopus citations

1995

Symmetric Logspace is Closed under Complement

Nisan, N. & Ta-Shma, A., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995. New York, NY, USA: Association for Computing Machinery, p. 140–146 7 p. (STOC '95).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Amnon Ta-Shma

Research output

Search results