WIGDERSON, AVI / Informatica / Investigadores

Centro Internacional de Investigación Científica


Informatica / WIGDERSON, AVI



Professor at the School of Mathematics, Institute of Advanced Study, Princeton, New Jersey, and Professor of Computer Science at the Institute for Computer Science in Jerusalem, Israel.

Randomness and Computation
Algorithms and Optimization
Complexity Theory
Circuit Complexity
Proof Complexity
Quantum Computation and Communication
Cryptography and Distributed Computation.

* The Yoram Ben-Porat Presidential Prize for outstanding Researcher
* Nevanlinna Prize, 1994.
* Invited speaker at the International Congress of Mathematicians , Zurich, Switzerland, 1994.
* Invited speaker at the International Congress of Mathematicians , Kyoto, Japan 1990.
* Bergman Fellowship, 1989.
* Alon Fellowship, 1986-1989.
* IBM Graduate Fellowship, Princeton University, 1982-1983.
* President's List of Excellence, The Technion, 1977-1980.

R. Armoni, A. Ta-Shma, A. Wigderson, S. Zhou, An 0(log(n) 4/3 ) space algorithm for (s; t) connectivity in undirected graphs, J. ACM Vol. 47, No. 2, 294{311, 2000.

L. Babai, A. Gal, A. Wigderson, Superpolynomial lower bounds for monotone span programs., Combinatorica Vol. 19, No. 3, 301-319, 1999.

A. Wigderson, D. Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications. Combinatorica Vol. 19, No. 1,
125-138, 1999.

Y. Rabinovich, A. Wigderson, Techniques for bounding the convergence rate of genetic algorithms. Random Structures Algorithms Vol. 14, No. 2, 111-138, 1999.

O. Reingold, S. Vadhan, A. Wigderson Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders, Annals of Math, Vol 155, No 1 157-187, 2002.

A. Shpilka, A. Wigderson Depth-3 Arithmetic Formulae over Fields of Characteristic Zero, Journal of Computational Complexity, Vol 10, No 1,
1-27, 2001.

E. Ben-Sasson, A. Wigderson Space Complexity in Propositional Calculus, SIAM Journal of Computing, 31 No 4, 1184-1211, 2001.

A. Wigderson On the Work of Madhu Sudan, Notices of the AMS, 50, No 1, 45-50, 2003.

J. Hastad, A. Wigderson Simple Analysis of Graph Tests for Linearity and PCP, Random Structures and Algorithms, Vol 22, No 2, 139-160, 2003.

R. Impagliazzo, V. Kabanets, A. Wigderson In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time, JCSS, Vol 65, No 4,
672-694, 2002.

E. Ben-Sasson, R. Impagliazzo, A. Wigderson Near Optimal Separation of Tree-Like and General Resolution, Combinatorica, Volume 24, Issue 4,
585-604, 2003.

A. Ambainis, L. Schulman, A. Ta-Shma, Vazirani, A. Wigderson, The Quantum Communication Complexity Sampling, Siam Journal on Computing,
Vol 32, No 6, 1570-1585, 2003.

A. Razborov, A. Wigderson, A. Yao, Read-once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Cal-
culus, Combinatorica, Vol 22, No 4, 555-574, 2003.

R. Meshulam, A. Wigderson Expanders in Group Algebras, Combinatorica, Volume 24, Issue 4, 659-680, 2003.

M. Alekhnovitch, E. Ben-Sasson, A. Razborov, A. Wigderson, Pseudo-random Generators in Propositional Proof Complexity, SIAM Journal on
Computing, Vol 34, Number 1, 2004.

Aviso legal - Contacto

Copyright © 2013 - www.cirs.info - Todos los derechos reservados