Avi Wigderson's Home Page
(Last updated on March 11, 2010)- P. Hrubes, A. Wigderson, A. Yehudayoff.
- Non-commutative circuits and the sum-of-squares problem
ECCC Report TR10-021, 2010- Accepted for STOC 2010
-
- P. Hrubes, A. Wigderson, A. Yehudayoff.
- Relationless completeness and separations
ECCC Report TR10-040, 2010- Accepted for CCC 2010
[ Journal version (pdf)
] -
- B. Barak, G. Kindler, Shaltiel, B. Sudakov, A. Wigderson.
- Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers and Extractors
Accepted JACM
-
- R. Impagliazzo, V. Kabanets, A. Wigderson.
- New Direct-Product Testers and 2-Query PCPs
Proceedings of STOC 09- ECCC Report TR09-090, 2009
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] -
- S. Arora, D. Steurer, A. Wigderson.
- Towards a study of low-complexity graphs
Proceedings of ICALP 2009
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Chattopadhyay, A. Wigderson.
- Linear systems over composite moduli
Proceedings of FOCS 09
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [ Journal version (pdf)
] [bibTeX entry]-
- Z. Dvir, A. Wigderson.
- Monotone expanders - constructions and applications
ECCC Report TR09-135, 2009
- (Abstract)
-
- R. Impagliazzo, R. Jaiswal, V. Kabanets, A. Wigderson.
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
Proceedings of STOC 08, pp. 579-588, 2008.- SIAM J. Comput., vol. 39, no. 4, pp. 1637-1665, 2010.
- (Abstract)
[ Journal version (pdf)
] [bibTeX entry]-
- B. Applebaum, B. Barak, A. Wigderson.
- Public Key Cryptography from Different Assumptions
Proceedings of STOC 2010
[ Draft of final version (pdf)
] -
- G. Kindler, A. Rao, Ryan O'Donnell, A. Wigderson.
- Spherical Cubes and Rounding in High Dimensions
Proceedings of the 49th Annual FOCS08, pp. 189-198, 2008.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] -
- V. Guruswami, J. Lee, A. Wigderson.
- Euclidean sections of l1N with sublinear randomness and error-correction over the reals
RANDOM '08
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] -
- S. Hoory, N. Linial, A. Wigderson.
- Expander graphs and their applications
Bulletin of the American Mathematical Society, vol. 43, no. 4, pp. 439-561, 2006.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Wigderson, D. Xiao.
- Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications
Theory of Computing, vol. 4 (2008), article 3, pp. 53-76.- ECCC Report TR06-105, 2006
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- E. Viola, A. Wigderson.
- Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols
Proceedings of the CCC07, pp. 141-154, 2007.- Theory of Computing, vol. 4, Article 7, pp. 137-168, 2008.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- S. Aaronson, A. Wigderson.
- Algebrization: A New Barrier in Complexity Theory
Proceedings of STOC 08, pp. 731-740, 2008.
- (Abstract)
[ Accepted to Theory of Computation (pdf)
] [ Accepted to Theory of Computation (ps)
] [bibTeX entry]-
- Z. Dvir, A. Wigderson.
- Kakeya sets, new mergers and old extractors
Proceedings of the 49th Annual FOCS08, pp. 625-633, 2008.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [ Journal version (pdf)
] -
- E. Viola, A. Wigderson.
- One-way multi-party communication lower bound for pointer jumping with applications
Proceedings of the FOCS 07 conference, pp. 427-437, 2007.- ECCC Report TR07-079, 2007
- (Abstract)
[ Full version (pdf)
] [ Full version (ps)
] [ Proceedings version (pdf)
] [ Proceedings version (ps)
] [ Final version (pdf)
] [ Final version (ps)
] [bibTeX entry]-
- A. Wigderson.
- P, NP and Mathematics - a computational complexity perspective
Proceedings of the ICM 06 (Madrid), vol. 1, EMS Publishing House, Zurich, pp. 665-712, 2007.
- (Abstract)
[ Proceedings version(pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- G. Kalai, A. Wigderson.
- Neighborly Embedded Manifolds
Discrete and Computational Geometry, 2008.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- Z. Dvir, A. Gabizon, A. Wigderson.
- Extractors and rank extractors for polynomial sources
Proceedings of the FOCS 07 conference, pp. 52-62, 2007.- ECCC Report TR07-056, 2007
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [ Full version (pdf)
] [ Full version (ps)
] [bibTeX entry]-
- R. Impagliazzo, R. Shaltiel, A. Wigderson.
- Reducing the seed length in the Nisan-Wigderson generator
Combinatorica, vol. 26, no. 6, pp. 647-681, 2006.
- (Abstract)
[ Full version (pdf)
] [ Full version (ps)
] [bibTeX entry]-
- B. Barak, A. Rao, R. Shaltiel, A. Wigderson.
- 2-Source Dispersers for Sub-Polynomial Entropy and Ramsey Graphs Beating the Frankl-Wilson Construction
Proceedings of STOC 06, pp. 671-680, 2006.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- E. Rozenman, A. Shalev, A. Wigderson.
- Iterative construction of Cayley expander graphs
Theory of Computing, vol. 2, no. 5, pp. 91-120, 2006. A shorter version appeared in STOC 04.
- (Abstract)
[ Final version (pdf)
] [ Final version (ps)
] [bibTeX entry]-
- I. Dinur , M. Sudan, A. Wigderson.
- Robust local testability of tensor products of LDPC codes
Proceedings of the 2006 RANDOM conference, pp. 304-315, 2006. - ECCC Report TR06-118, 2006
- (Abstract)
[ Proceedings version(pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- J. Hastad, A. Wigderson.
- Simple Analysis of Graph Tests
Conference on Computational Complexity, pp. 244-255, 2001. (see also ECCC)
- (Abstract)
[ Draft of final version May 11, 2001 (pdf)
] [ Draft of final version May 11, 2001 (ps)
] [bibTeX entry]-
- O. Reingold, R. Shaltiel, A. Wigderson.
- Extracting Randomness via Repeated Condensing
Proceedings of the 41st FOCS, pp. 22-31, 2000 - SIAM Journal on Computing, vol. 35, no. 5, pp. 1185-1209, 2006.
- (Abstract)
[ Final version (pdf)
] [ Final version (ps)
] [bibTeX entry]-
- A. Wigderson, D. Xiao.
- A randomness-efficient sampler for matrix-valued functions and applications
46th Annual Symposium of FOCS 2005, pp. 397-406, 2005.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- P. Beame, T. Pitassi, N. Segerlind, A. Wigderson.
- A Strong Direct Product Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
CCC05, pp 52-66, 2005.- Computational Complexity, vol. 15, no. 4, pp. 391-432, 2006.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- B. Barak, R. Impagliazzo, A. Wigderson.
- Extracting randomness using few independent sources
Proceedings of the 45th FOCS 2004, pp. 384-393, 2004.- SICOMP, vol. 36, no. 4, pp. 1095-1118, 2006.
- (Abstract)
[ Final journal version (pdf)
] [ Final journal version (ps)
] [bibTeX entry]-
- R. Meshulam, A. Wigderson.
- Expanders in Group Algebras
Combinatorica, vol. 24, no. 4, pp 659-680, 2004.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- E. Ben-Sasson, R. Impagliazzo, A. Wigderson.
- Near Optimal Separation of Tree-like and General Resolution
Combinatorica, vol. 24, no. 4, pp. 585-604, 2004.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- E. Rozenman, A. Shalev, A. Wigderson.
- A new family of Cayley expanders (?)
36th Annual ACM Symposium, STOC 2004, pp. 445-454, 2004.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, A. Wigderson.
- Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors
Proceedings of the 46th STOC 05, pp. 1-10, 2005.
- (Abstract)
[ Full version (pdf)
] [ Full version (ps)
] [bibTeX entry]-
- M. Alekhnovitch, E. Ben-Sasson, A. Razborov, A. Wigderson.
- Pseudorandom Generators in Propositional Proof Complexity
SIAM Journal on Computing, vol. 34, no. 1, pp. 67-88, 2004. Preliminary version appeared in STOC2000.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Shpilka, A. Wigderson.
- Derandomizing homomorphism testing in general groups
36th Annual ACM Symposium, STOC 2004, pp. 427-435, 2004. - SICOMP, vol. 36, no. 4, pp. 1215-1230, 2006.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson.
- The Quantum Communication Complexity of Sampling
SIAM Journal on Computing, vol. 32, no. 6, pp 1570-1585, 2003.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- C-J Lu, O. Reingold, S. Vadhan, A. Wigderson.
- Extractors: Optimal up to Constant Factors
35th Annual ACM Symposium, STOC 2003, pp. 602-611, 2003.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- B. Barak, R. Shaltiel, A. Wigderson.
- Computational Analogues of Entropy
11th International Conference on Random Structures and Algorithms, pp. 200-215, August 2003.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- E. Ben-Sasson, M. Sudan, S. Vadhan, A. Wigderson.
- Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets
35th Annual ACM Symposium, STOC 2003, pp. 612-621, 2003.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- O. Goldreich, S. Vadhan, A. Wigderson.
- On Interactive Proofs With a Laconic Power
Journal of Computational Complexity, vol. 2076, p. 334, 2003.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Razborov, A. Wigderson, A. Yao.
- Read-once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus
Combinatorica, vol. 22, no. 4, pp. 555-574, 2003.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- J. Hastad, A. Wigderson.
- Simple Analysis of Graph Tests for Linearity and PCP
Random Structures and Algorithms, vol. 22, no. 2, pp 139-160, 2003.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- O. Reingold, S. Vadhan, A. Wigderson.
- Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders
Annals of Mathematics, vol. 155, no.1, pp. 157-187, 2002.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Impagliazzo, V. Kabanets, A. Wigderson.
- In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time
JCSS, vol. 65, no. 4, pp 672-694, 2002.- Conference on Computational Complexity, pp. 2-12, 2001.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- E. Friedgut, J. Kahn, A. Wigderson.
- Computing Graph Properties by Randomized Subcube Partitions
Randomization and Approximation Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp. 105-113, 2002.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson.
- Randomness Conductors and Constant-Degree Expansion Beyond the Degree /2 Barrier
Proceedings of the 34th STOC, pp. 659-668, 2002.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- O. Goldreich, A. Wigderson.
- Derandomization that is Rarely Wrong from Short Advice that is Typically Good
Randomization and Approximation Techniques in Computer Science, 6th International Workshop, RANDOM 2002, pp. 209-223, 2002.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- A. Wigderson.
- On the Work of Madhu Sudan.no 1, pp. 45-50, 2003.
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- M. Alekhnovitch, E. Ben-Sasson, A. Razborov, A. Wigderson.
- Space Complexity in Propositional Calculus
SIAM Journal of Computing, vol. 31, no. 4, pp. 1184-1211, 2001. Preliminary version appeared in STOC 2000.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- O. Goldreich, S. Vadhan, A. Wigderson.
- On Interactive Proofs with a Laconic Power
Proceedings of the 28th ICALP, pp. 334-345, 2001.
- (Abstract)
[ Draft of final version September 5, 2001 (pdf)
] [ Draft of final version September 5, 2001 (ps)
] [bibTeX entry]-
- N. Alon, A. Lubotzky, A. Wigderson.
- Semi-direct product in groups and Zig-zag product in graphs: Connections and applications
Proceedings of the 42nd FOCS, pp. 630-637, 2001.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- O. Goldreich, A. Wigderson.
- On Pseudorandomness with respect to Deterministic Observers
Proceedings of the satellite workshops of the 27th ICALP, Carleton Scientific (Proc. in Informatics 8), pp. 77-84, 2000.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Armoni, A. Ta-Shma, A. Wigderson, S. Zhou.
- A (log n )^{4/3} space algorithm for (s,t) connectivity in undirected graphs
Preliminary version in Proceedings of the 29th STOC, pp. 230-239, 1997. - J. ACM, vol. 47, no. 2, 294-311, 2000.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Impagliazzo, R. Shaltiel, A. Wigderson.
- Extractors and Pseudo-random Generators with Optimal Seed Length
Proceedings of the 32nd STOC, pp. 1-10, 2000.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- O. Reingold, S. Vadhan, A. Wigderson.
- Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Proceedings of the 41st FOCS, pp. 3-13, 2000.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- Y. Rabinovich, A. Wigderson.
- Techniques for bounding the convergence rate of genetic algorithms.
Random Structures Algorithms, vol. 14, no. 2, 111-138, 1999.
- (Abstract)
[ Journal version (ps)
] [ Journal version (pdf)
] [bibTeX entry]-
- A. Wigderson, D. Zuckerman.
- Expanders that beat the eigenvalue bound: explicit construction and applications
Combinatorica, vol. 19, no. 1, 125-138, 1999.- Preliminary version in Proceedings of the 25th STOC, pp. 245-251, 1993.
- (Abstract)
[ Journal version (ps)
] [ Journal version (pdf)
] [bibTeX entry]-
- E. Ben-Sasson, A. Wigderson.
- Short Proofs are Narrow - Resolution made Simple
Proceedings of the 31th STOC, pp. 517-526, 1999.- Journal of the ACM, vol. 48, no. 2, 2001.
- ECCC Report TR99-022, 1999.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Impagliazzo, R. Shaltiel, A. Wigderson.
- Near-optimal Conversion of Hardness into Pseudo-randomness
Proceedings of the 40th FOCS, pp. 181-190, 1999.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- L . Babai, A. Gal, A. Wigderson.
- Superpolynomial lower bounds for monotone span programs.
Combinatorica, vol. 19, no. 3, 301-319, 1999.
- (Abstract)
[ Journal version (ps)
] [ Journal version (pdf)
] [bibTeX entry]-
- O. Goldreich, A. Wigderson.
- Improved derandomization of BPP using a hitting set generator
Proceedings of the RAMDOM 99 Conference, pp. 131-137, 1999.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Shpilka, A. Wigderson.
- Depth-3 Arithmetic Formulae over Fields of Characteristic Zero
Accepted to Journal of Computational Complexity, vol. 10, no. 1, pp. 1-27, 2001.- Preliminary version in Proceedings of the 14th Conference on Computational Complexity, pp. 87-97, 1999.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- Z. Bar-Yossef, O. Goldreich, A. Wigderson.
- Deterministic Amplification of Space-Bounded Probabilistic Algorithms
Proceedings of the 14th Conference on Computational Complexity, pp. 188-199, 1999.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Impagliazzo, A. Wigderson.
- Randomness vs. Time: De-randomization under a uniform assumption
Proceedings of the 39th FOCS, pp.734-743, 1998.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- H. Buhrman, R. CLeve, A. Wigderson.
- Quantum vs. Classical Communication and Computation
Proceedings of 30th STOC, pp. 63-68, 1998.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Condon, L. Hellerstein, S. Pottle, A. Wigderson.
- Finite State Automata with Nondeterministic and Probabilistic States
SIAM J. on Computing, vol. 27, no. 3, pp. 739-762, June 1998.- Proceedings of the 26th STOC, pp. 676-685, 1994.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson.
- The Quantum Communication Complexity of Sampling
Siam Journal on Computing, vol. 32, pp. 1570-1585, 2003.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- N. Linial, A. Samorodnitsky, A. Wigderson.
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
Proceedings of 30th STOC, pp. 644-652, 1998.- Combinatorica, 20, 4, 2000.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- P. Miltersen, N. Nisan, S. Safra, A. Wigderson.
- On Data Structures and Asymmetric Communication Complexity
JCSS, vol. 57, no. 1, pp. 37-49, 1998. - Preliminary version appeared in Proceedings of the 27th STOC, pp. 103-111, 1995.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Impagliazzo, A. Wigderson.
- P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma
Proceedings of the 29th STOC, pp. 220-229, 1997.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Razborov, A. Wigderson, A. Yao.
- Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and Transversal Calculus
Proceedings of the 29th STOC, pp. 739-748, 1997.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- O. Goldreich, A. Wigderson.
- Tiny Families of Functions with Random Properties: A Quality-Size Trade-off
Random Structures and Algorithms, vol. 11, no. 4, pp. 315-343, 1997.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- I. Parnafes, R. Raz, A. Wigderson.
- Direct Product Results and the GCD Problem, in Old and New Communication Models
Proceedings of the 29th STOC, pp. 363-372, 1997.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- L . Babai, A. Gal, J. Kollar, L. Ronyai, T. Szabo, A. Wigderson.
- Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs
Proceedings of 28th STOC, pp. 603-611, 1996.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- N. Nisan, A. Wigderson.
- Lower Bounds on Arithmetic Circuits via Partial Derivatives
Preliminary version in Proceedings of the 36th FOCS, pp. 16-25, 1995.- Computational Complexity, vol. 6, pp. 217-234, 1996.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Sharan, A. Wigderson.
- A New NC Algorithm for Perfect Matching in Bipartite Cubic Graphs
Proceedings of ISTCS 96, pp. 56-65, 1996.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Armoni, M. Saks, A. Wigderson, S. Zhou.
- Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles
Proceedings of the 37th FOCS, pp. 412-421, 1996.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- O. Goldreich, A. Wigderson.
- On the Circuit Complexity of Perfect Hashing
ECCC Report TR96-041
-
- I. Newman, A. Wigderson.
- Lower Bounds on Formula Size of Boolean Functions using Hypergraph Entropy
SIAM Journal on Discrete Mathematics, vol. 8 no. 4, pp. 78-87, 1996.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Gal, A. Wigderson.
- Boolean Complexity Classes vs. Their Arithmetic Analogs
Random Structures and Algorithms, vol. 9, pp. 1-13, 1996.- ECCC Report TR05-049, 1995
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- Y. Gil, F. Meyer auf der Heide, A. Wigderson.
- The Tree Model for Hashing: Lower and Upper Bounds
SIAM J. on Computing, vol. 10, pp. 936-955, 1996.- Preliminary version in Proceedings of the 22nd STOC, pp. 244-253, May 1990.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- H. Alt, L. Guibas, R. Karp, K. Mehlhorn, A. Wigderson.
- A Method for Obtaining Probabilistic Algorithms with Small Tail Probabilities
Algorithmica, vol. 16, no. 4-5, pp. 543-547, 1996.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- N. Nisan, A. Wigderson.
- A note on Rank vs. Communication Complexity
Combinatorica, vol. 15, no. 4, pp. 557-566, 1995.- Also appeared in Proceedings of the 35th FOCS, pp. 831-836, 1994.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- J. Friedman, A. Wigderson.
- On the Second Largest Eigenvalue of Hypergraphs
Combinatorica, vol. 15, no. 1, pp. 43-65, 1995.
[ Journal version (pdf)
] [ Journal version (ps)
] -
- I. Damgard, O. Goldreich, Okamoto , A. Wigderson.
- Honest Verifier vs. Dishonest Verifier in Public Coin Zero-Knowledge Proofs
Advances in Cryptology - Crypto `95 (Proceedings), Lecture Note in Computer Science (963), Springer-Verlag, pp. 325-338, 1995.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- M. Karchmer, R. Raz, A. Wigderson.
- Super-Logarithmic Depth Lower Bounds via Direct Sum in Communication Complexity
Computational Complexity, vol. 5, pp. 191-204, 1995.- Preliminary version Proceedings of the 6th Structures in Complexity Theory conference, pp. 299-304, July 1991.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- N. Nisan, A. Wigderson.
- On the Complexity of Bilinear Forms
Proceedings of the 27th STOC, pp. 723-732, 1995.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- N. Alon, U. Feige, A. Wigderson, D. Zuckerman.
- Derandomized Graph Products
Computational Complexity, pp. 60-75, 1995.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- L. Lovasz, I. Newman, M. Naor, A. Wigderson.
- Search Problems in the Decision Tree Model
SIAM J. on Discrete Math., vol. 8, pp. 119-132, 1995. (Preliminary version appeared at Proceedings of the 32nd FOCS conference, pp. 576-585, 1991.)
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- O. Goldreich, N. Nisan, A. Wigderson.
- On Yao's XOR-Lemma
- (Abstract)
[ manuscript (pdf)
] [ manuscript (ps)
] -
- A. Wigderson.
- NL/poly
L/poly
Proceedings of the 9th Structures in Complexity Conference, pp. 59-62, July 1994.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson.
- On the Power of Randomization in On-line Algorithms
Algorithmica, vol. 11, no. 1, pp. 2-14, 1994.- Proceedings of the 22nd STOC, pp. 379-388, May 1990.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Impagliazzo, N. Nisan, A. Wigderson.
- Pseudorandomness for Network Algorithms
Proceedings of the 26th STOC, pp. 356-364, 1994.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- N. Nisan, A. Wigderson.
- Hardness vs. Randomness
Journal of Computer Systems and Sciences, vol. 49, no. 2, pp. 149-167, 1994.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- O. Goldreich, A. Wigderson.
- Tiny Families of Functions with Random Properties: A Quality-Size Trade-off
Proceedings of the 26th STOC, pp. 574-583, 1994.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- M. Karchmer, I. Newman, M. Saks, A. Wigderson.
- Non-deterministic Communication Complexity with Few Witnesses
JCSS, vol. 49, no. 2, pp. 247-257, 1994.- Also appeared in 7th Structures in Complexity Theory Conference, pp. 275-281, 1992.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- N. Nisan, A. Wigderson.
- Rounds in Communication Complexity Revisited
SIAM Journal on Computing, vol. 22, no. 1, pp. 211-219, 1993.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Ostrovsky, A. Wigderson.
- Nontrivial Zero-Knowledge Implies One-Way Functions
Proceedings of the 2nd ISTCS, pp. 3-17, 1993.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- M. Karchmer, N. Linial, I. Newman, M. Saks, A. Wigderson.
- Combinatorial Characterization of Read-Once Formulae
J. Discrete Math. vol. 114, pp. 275-282, 1993.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- M. Karchmer, A. Wigderson.
- On Span Programs
Proceedings of the 8th Structures in Complexity conference, pp. 102-111, 1993.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- M. Luby, B. Velickovic, A. Wigderson.
- Deterministic Approximate Counting of Depth-2 Circuits
Proceedings of the 2nd ISTCS (Israeli Symposium on Theoretical Computer Science), pp. 18-24, 1993.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- L . Babai, L. Fortnow, N. Nisan, A. Wigderson.
- BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs
Complexity Theory, vol. 3, pp. 307-318, 1993.- Proceedings of the 6th Structures in Complexity Theory Conference, pp. 213-19, July 1991.
- (Abstract)
[ Journal version (pdf
] [ Journal version (ps
] [bibTeX entry]-
- A. Razborov, E. Szemeredi, A. Wigderson.
- Constructing Small Sets that are Uniform in Arithmetic Progressions
Probability, Combinatorics and Complexity, vol. 2, pp. 513-518, 1993.
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Razborov, A. Wigderson.
-
Lower Bounds on the Size of Depth 3 Threshold Circuits with AND Gates at the Bottom
IPL, vol. 45, pp. 303-307, 1993.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Wigderson.
- The Fusion Method for Lower Bounds in Circuit Complexity
Combinatorics, Paul Erdos is Eighty (vol. 1), Miklos, Sos and Szonyi (Eds.), Bolyai Math. Society, pp. 453-468, 1993.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- S. Hoory, A. Wigderson.
- Universal Sequences for Expander Graphs
Information Processing Letters, vol. 46, no. 2, pp. 67-69, 1993.
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- M. Karchmer, A. Wigderson.
- On Characterizing Nondeterministic Circuit Size
Proceedings of the 25th STOC, pp. 532-545, 1993.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Wigderson.
- The Complexity of Graph Connectivity
Proceedings of the 17th Mathematical Foundations of Computer Science conference, Havel and Koubek (eds.), Lecture Notes in Computer Science 629, Springer-Verlag, pp. 112-132, 1992.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- Y. Gil, W. Steiger, A. Wigderson.
- Geometric Medians
Discrete Math, vol. 108, no. 1, pp. 37-51, 1992.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- Y. Rabinovich, A. Sinclair, A. Wigderson.
- Quadratic Dynamical Systems
Proceedings of the 33rd FOCS conference, pp. 304-313, 1992.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- R. Raz, A. Wigderson.
- Monotone Circuits for Matching require Linear Depth
Journal of the ACM, vol. 39, pp. 736-744, 1992.- Preliminary version in Proceedings of the 22nd STOC, pp. 287-292, May 1990.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- P. Ragde, A. Wigderson.
- Linear-Size Constant-Depth Polylog- Threshold Circuits,
Information Processing Letters, vol. 39, no. 3, pp. 143-46, 1991.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- Y. Rabinovich, A. Wigderson.
- An Analysis of a Simple Genetic Algorithm
Proceedings of the 4th International Conference on Genetic Algorithms, pp. 215-221, July 1991.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- P. Gemmell, R. Lipton, R. Rubinfeld, Sudan , A. Wigderson.
- Self Testing / Correcting for Polynomials and for Approximate Functions
Proceedings of the 23rd STOC, pp. 32-42, May 1991.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- O. Goldreich, S. Micali, A. Wigderson.
- Proofs that Yield Nothing but their Validity, or All Languages in NP have Zero-Knowledge Proof Systems
Journal of the ACM, vol. 38, no. 1, pp. 691-729, 1991.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- N. Nisan, A. Wigderson.
- Rounds in Communication Complexity Revisited
Proceedings of the 23rd STOC, pp. 419-429, May 1991.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Heiman , A. Wigderson.
- Randomized vs. Deterministic Decision Tree Complexity for Read-Once Boolean Functions
Proceedings of the 6th Structures in Complexity Theory Conference, pp. 172-179, July 1991.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Heiman, A. Wigderson.
- Randomized vs. Deterministic Decision Tree Complexity for Read-Once Boolean Functions
Complexity Theory, vol. 1, pp. 311-329, 1991.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- L. Lovasz, I. Newman, M. Naor, A. Wigderson.
- Search Problems in the Decision Tree Model
Proceedings of the 32nd FOCS conference, pp. 576-585, 1991.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Heiman, I. Newman, A. Wigderson.
- On Read-Once Threshold Formulae and their Randomized Decision Tree Complexity
5th Structures in Complexity Theory, pp. 78-89, July 1990.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- F. Fich, A. Wigderson.
- Towards Understanding Exclusive Reads
SIAM Journal on Computing, vol. 19, no. 4, pp. 718-727, 1990.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- F. Fich, A. Wigderson.
- Towards Understanding Exclusive Read
Proceedings of 1st Symposium on Parallel Algorithms and Architectures, pp. 718-727, August 1990.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Wigderson.
- Information Theoretic Reasons for Computational Difficulty
Proceedings of the International Congress of Mathematicians, pp. 1537-1548, August 1990.
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- M. Karchmer, A. Wigderson.
- Monotone Circuits for Connectivity require Super-Logarithmic Depth
SIAM Journal on Discrete Mathematics, vol. 3, no. 2, pp. 255-65, 1990.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Heiman, I. Newman, A. Wigderson.
- On Read-Once Threshold Formulae and their Randomized Decision Tree Complexity,
Theoretical Computer Science, vol. 107, no. 1, pp. 63-76, 1990.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- Y. Gil, F. Meyer auf der Heide, A. Wigderson.
- Not All Keys can be Hashed in Constant Time
Proceedings of the 22nd STOC, pp 244-253, May 1990.
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- N. Alon, M. Karchmer, A. Wigderson.
- Linear Circuits over GF(2)
SIAM Journal on Computing, vol. 19, no. 6 pp. 1064-067, 1990.
- (Abstract)
[ Journal version (pdf)
] [ Journal Version (ps)
] [bibTeX entry]-
- I. Newman, P. Ragde, A. Wigderson.
- Perfect Hashing, Graph Entropy and Circuit Complexity
Proceedings of the 5th Structures in Complexity Theory Conference, pp. 91-99, July 1990.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- M. Ajtai, A. Wigderson.
- Deterministic Simulation of Probabilistic Constant-Depth Circuits
Advances in Computing Research - Randomness and Computation, Eds F. Preparata and S. Micali, vol. 5, pp. 199-23, 1989.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- J. Hastad, A. Wigderson.
- Composition of the Universal Relation
Advances in Computational Complexity Theory, AMS-DIMACS book series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 119-134, 1993.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps
] [bibTeX entry]-
- M. Ben-Or, S. Goldwasser, J. Kilian, A. Wigderson.
- Efficient Identification Schemes Using Two Prover Interactive Proofs
Advances in Cryptography, CRYPTO 89, LNCS 435, Springer-Verlag, pp. 498-506, 1989.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Cohen, A. Wigderson.
- Dispersers, Deterministic Amplification and Weak Random Sources
Proceedings of the 30th FOCS, pp. 14-19, 1989.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Raz, A. Wigderson.
- Probabilistic Communication Complexity of Boolean Relations
Proceedings of the 30th FOCS, pp. 562-567, 1989.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- N. Nisan, E. Szemeredi, A. Wigderson.
- Undirected Connectivity in
Space
Proceedings of the 30th FOCS conference, pp. 24-29, 1989.
- (Abstract)
[ Draft of final version (pdf)
] [ Draft of final version (ps)
] [bibTeX entry]-
- R. Karp, E. Upfal, A. Wigderson.
- The Complexity of Parallel Search
Journal of Computer and System Sciences, vol. 36, no. 2, pp. 225-253, 1988.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- P. Ragde, W. Steiger, E. Szemeredi, A. Wigderson.
- The Parallel Complexity of Element Distinctness is
SIAM Journal on Discrete Mathematics, vol. 1, no. 3, pp. 399-410, 1988.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- D. Long, A. Wigderson.
- The Discrete Logarithm Hides O(log n) Bits
SIAM Journal on Computing, vol. 17, no. 2, pp. 363-372, 1988.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- F. Fich, P. Ragde, A. Wigderson.
- Simulations among Concurrent-Write PRAMs
Algorithmica, vol. 3, pp. 43-51, 1988.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- F. Fich, P. Ragde, A. Wigderson.
- Relations between Concurrent-Write Models of Parallel Computation
SIAM Journal on Computing, vol. 17, no. 3, pp. 606-627, 1988.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
- A tradeoff between Search and Update Time for the Implicit Dictionary Problem
Theoretical Computer Science, vol. 58, pp. 57-68, 1988.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- N. Linial, L. Lovasz, A. Wigderson.
- Rubber Bands, Convex Embeddings and Graph Connectivity
Combinatorica, vol. 8, pp.91-102, 1988.
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
- A Time-Space Tradeoff for Element Distinctness
Proceedings of STACS Conference, Lecture Notes in Comp. Sci., Springer Verlag, vol. 210, pp. 353-358, 1986.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- B. Yust, F. Meyer auf der Heide, A. Wigderson.
- On Computations with Integer Division
Proceedings of the STACS conference, pp. 29-37, 1988.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- S. Goldwasser, J. Kilian, M. Ben-Or, A. Wigderson.
- Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
Proceedings of the 20th STOC, pp. 113-131, May 1988.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- S. Goldwasser, M. Ben-Or, A. Wigderson.
- Completeness Theorems for Non-cryptographic Fault-tolerant Distributed Computing
Proceedings of the 20th STOC, pp. 1-10, May 1988.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- M. Karchmer, A. Wigderson.
- Monotone Connectivity Circuits require Super-logarithmic Depth
Proceedings of the 20th STOC, pp. 539-550, May 1988.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- N. Nisan, A. Wigderson.
- Hardness vs. Randomness
Proceedings of the 29th FOCS, pp. 2-11, 1988.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
- A Time-Space Tradeoff for Element Distinctness
SIAM Journal on Computing, vol. 16, no. 1, pp. 97-99, February 1987.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- F. Fich, F. Meyer auf der Heide, A. Wigderson.
- Lower Bounds for Parallel Random Access Machines with Unbounded Shared Memory
Advances in Computing Research - Parallel and Distributed Computing, Ed. F. Preparata, vol. 4, pp. 1-6, 1987.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- F. Meyer auf der Heide, A. Wigderson.
- The Complexity of Parallel Sorting
SIAM Journal on Computing, vol. 16, no. 1, pp. 100-107, 1987.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- O. Goldreich, S. Micali, A. Wigderson.
- How to Play any Mental Game
Proceedings of the 19th STOC, pp. 218-229, May 1987.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] -
- O. Goldreich, S. Micali, A. Wigderson.
- Proofs that Yield Nothing but their Validity, and a Methodology of Cryptographic Protocol Design
Proceedings of the 27th FOCS, pp. 174-187, October 1986.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- E. Upfal, A. Wigderson.
- How to Share Memory in a Distributed System
Journal of the ACM, vol. 34, no. 1, pp.116-127, 1986.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Karp, E. Upfal, A. Wigderson.
- Constructing a Perfect Matching is in Random NC
Combinatorica, vol. 6, no. 1, pp. 35-48, 1986.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Karp, M. Saks, A. Wigderson.
- A Search Problem Related to Branch-and-Bound Procedures
Proceedings of the 27th FOCS, pp. 19-28, October, 1986.
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- N. Linial, L. Lovasz , A. Wigderson.
- A Physical interpretation of graph connectivity and its algorithmic applications
Proceedings of the 27th FOCS, pp.39-48, October 1986.
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson.
- A Trade-off Between Search and Update Time for the Implicit Dictionary Problem
Lecture Notes in Comp. Sci., Springer-Verlag, vol. 226, pp. 50-59, 1986.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- M. Perry, A. Wigderson.
- Search in a Known Pattern
Journal of Political Economy, vol. 94, no. 1, pp. 225-230, 1986.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- N. Megiddo, A. Wigderson.
- On Play by Means of Computing Machines
Conference on Theoretical Aspects of Reasoning about Knowledge, pp. 259-274, March 1986.
- (Abstract)
[ Proceedings Version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- M. Saks, A. Wigderson.
- Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees
Proceedings of the 27th FOCS, pp. 29-38, October 1986.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- U. Vishkin, A. Wigderson.
- Depth-Width Trade-offs in Parallel Processing
SIAM Journal on Computing, vol. 14, no. 2, pp. 303-314, May 1985.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Karp, E. Upfal, A. Wigderson.
- Constructing a Perfect Matching is in Random NC
Proceedings of the 17th STOC, pp. 22-32, May 1985.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Karp, A. Wigderson.
- A Fast Parallel Algorithm for the Maximal Independent Set Problem
Journal of the ACM, vol. 32, no. 4, pp.762-773, October 1985.- Preliminary version in Proceedings of the 16th STOC, pp. 266-272, May 1984.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- M. Ajtai, A. Wigderson.
- Deterministic Simulation of Probabilistic Constant- Depth Circuits
Proceedings of the 26th FOCS, pp. 11-19, October 1985.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- Vijayan, A. Wigderson.
- Rectilinear Graphs and their Embedding
SIAM Journal on Computing, vol. 14, no. 2, pp. 355-372, May 1985.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- R. Karp, E. Upfal, A. Wigderson.
- The Complexity of Parallel Computation on Matroids
Proceedings of the 26th FOCS, pp. 541-550, October 1985.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- F. Fich, F. Meyer auf der Heide, P. Ragde, A. Wigderson.
- One, Two, Three...Infinity: Lower Bounds for Parallel Computation
Proceedings of the 17th STOC, pp. 48-58, May 1985.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- F. Meyer auf der Heide, A. Wigderson.
- The Complexity of Parallel Sorting
Proceedings of the 26th FOCS, pp. 532-540, October 1985.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- R. Karp, E. Upfal, A. Wigderson.
- Are Search and Decision Problems Computationally Equivalent?
Proceedings of the 17th STOC, pp. 464-475, May 1985.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial, A. Wigderson.
- Multilayer Grid Embedding
Proceedings of the 26th FOCS, pp. 186-196, October 1985.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- H. Galperin, A. Wigderson.
- Succinct Representation of Graphs
Information and Control, vol. 56, no. 3, pp. 183-198, March 1984.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- U. Vishkin, A. Wigderson.
- Dynamic Parallel Memories
Information and Control, vol. 56, no. 3, pp. 174-182, March 1984.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-
- F. Fich, P. Ragde, A. Wigderson.
- Relations Between Concurrent-Write Models of Parallel Computation
Conference on the 3rd ACM Symposium on Principles of Distributed Computation, pp. 75-88, 1984.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- E. Upfal, A. Wigderson.
- How to Share Memory in a Distributed System
Proceedings of the 25th FOCS, pp. 171-180, October 1984.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- D. Long, A. Wigderson.
- How Discreet is the Discrete Log?
Proceedings of the 15th STOC, pp. 413-420, May 1983.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- D. Dolev, C. Dwork, N. Pippenger, A. Wigderson.
- Superconcentrators, Generalizers, and Generalized Connectors with Limited Depth
Proceedings of the 15th STOC, pp. 42-51, May 1983.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- U. Vishkin, A. Wigderson.
- Depth-Width Trade-offs in Parallel Computation
Proceedings of the 24th FOCS, pp. 146-153, November 1983.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- Vijayan, A. Wigderson.
- Planarity of Edge Ordered Graphs
Technical Report #307, Department of EECS, Princeton University, December 1982.
- (Abstract)
[ Technical report (pdf)
] [ Technical report (ps)
] [bibTeX entry]-
- D. Dolev, A. Wigderson.
- The Security of Multi-Party Protocols in Distributed Systems
Proceedings of the Crypto 82 Conference, pp. 167-176, August 1982.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Wigderson.
- A New Approximate Graph Coloring Algorithm
Proceedings of the 14th STOC, pp. 325-329, May 1982.
- (Abstract)
[ Proceedings version (pdf)
] [ Proceedings version (ps)
] [bibTeX entry]-
- A. Wigderson.
- The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs
Technical Report #298, Department of EECS, Princeton University, February 1982.
[ Technical Report 298 (pdf)
] [bibTeX entry]-
- B. Yust, F. Meyer auf der Heide, A. Wigderson.
- On Computations with Integer Division
Theoretical Informatics and Applications, vol. 23, no. 1, pp. 101-111, 1989.
- (Abstract)
[ Journal version (pdf)
] [ Journal version (ps)
] [bibTeX entry]-