Avraham Ben-Aroya

I am a postdoctoral fellow at the Weizmann Institute hosted by Ran Raz.
I completed my Ph.D. studies at Tel-Aviv university under the supervision of Oded Regev and Amnon Ta-Shma.
I am broadly interested in theoretical computer science.
My research is focused on quantum computation, quantum information and pseudorandomness.

Contact information:

The Weizmann Institute of Science
Department of Applied Math and Computer Science
Rehovot 76100, ISRAEL
Tel.: 08-9343434
Office: Ziskind 205
E-mail: avraham.ben-aroya at weizmann d¿t ac d?t il

Publications:

• A Note on Subspace Evasive Sets [link]
  A. Ben-Aroya and I. Shinkar
• Gradual Small-Bias Sample Spaces [link]
  A. Ben-Aroya and G. Cohen
• A Note on Amplifying the Error-Tolerance of Locally Decodable Codes [link]
  A. Ben-Aroya, K. Efremenko and A. Ta-Shma
  
• Local list decoding with a constant number of queries [link]
  A. Ben-Aroya, K. Efremenko and A. Ta-Shma
  IEEE Symposium on Foundations of Computer Science (FOCS) 2010
• Better short-seed extractors against quantum knowledge [link]
  A. Ben-Aroya and A. Ta-Shma
  Theoretical Computer Science 419, 17-25, 2012
• Constructing Small-Bias Sets from Algebraic-Geometric Codes [pdf]
  A. Ben-Aroya and A. Ta-Shma
  IEEE Symposium on Foundations of Computer Science (FOCS) 2009
  Theory of Computing, to appear
• Approximate quantum error correction for correlated noise [link]
  A. Ben-Aroya and A. Ta-Shma
  Quantum Information Processing (QIP) 2009
  IEEE Transactions on Information Theory, 57(6), 3982-3988, 2011
• On the complexity of approximating the diamond norm [link]
  A. Ben-Aroya and A. Ta-Shma
  Quantum Information and Computation 10(1&2), 77-86, 2010
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs [link]
  A. Ben-Aroya, O. Regev and R. de Wolf
  IEEE Symposium on Foundations of Computer Science (FOCS) 2008
  Quantum Information Processing (QIP) 2008 (Invited talk)
• A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product [pdf]
  A. Ben-Aroya and A. Ta-Shma
  ACM Symposium on Theory of Computing (STOC) 2008
  SIAM Journal on Computing, 40(2), 267-290, 2011
• Quantum Expanders: Motivation and Constructions
  A. Ben-Aroya, O. Schwartz and A. Ta-Shma
  Theory of Computing 6(3), 47-79, 2010
  IEEE Conference on Computational Complexity (CCC) 2008
  Quantum Information Processing (QIP) 2008 (Invited talk)
  Based on:
  • Quantum Expanders and the Quantum Entropy Difference Problem [link]
    A. Ben-Aroya and A. Ta-Shma
    Quantum Information Processing (QIP) 2007
  • An Explicit Construction of Quantum Expanders [link]
    A. Ben-Aroya, O. Schwartz and A. Ta-Shma
    Technical report
• Competitive Analysis of Flash-memory Algorithms
  A. Ben-Aroya and S. Toledo
  European Symposium on Algorithms (ESA) 2006
  ACM Transactions on Algorithms 7(2), 23, 2011
• MSc thesis [pdf]