| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff |
Restriction access.  |
ITCS  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff |
Restriction Access. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Xi Chen, Neeraj Kayal, Avi Wigderson |
Partial Derivatives in Arithmetic Complexity and Beyond. |
Foundations and Trends in Theoretical Computer Science |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Avi Wigderson |
Kakeya Sets, New Mergers, and Old Extractors. |
SIAM J. Comput. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Noam Nisan, Avi Wigderson |
On Yao's XOR-Lemma. |
Studies in Complexity and Cryptography |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Salil P. Vadhan, Avi Wigderson |
Simplified Derandomization of BPP Using a Hitting Set Generator. |
Studies in Complexity and Cryptography |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Avi Wigderson |
On the Circuit Complexity of Perfect Hashing. |
Studies in Complexity and Cryptography |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson |
Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
Non-commutative circuits and the sum-of-squares problem. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson |
Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
Relationless completeness and separations. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff |
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Zeev Dvir, Avi Wigderson |
Monotone Expanders: Constructions and Applications. |
Theory of Computing |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson |
Simulating independence: New constructions of condensers, ramsey graphs, dispersers, and extractors. |
J. ACM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff |
Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson |
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. |
SIAM J. Comput. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Avi Wigderson |
Symmetric LDPC Codes and Local Testing. |
Property Testing |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Avi Wigderson |
Symmetric LDPC Codes and Local Testing. |
ICS |
2010 |
DBLP BibTeX RDF |
|
| 1 | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
Relationless Completeness and Separations. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Completeness, Separations, Algebraic complexity |
| 1 | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
Non-commutative circuits and the sum-of-squares problem. |
STOC |
2010 |
DBLP DOI BibTeX RDF |
lower bounds, algebraic complexity |
| 1 | Benny Applebaum, Boaz Barak, Avi Wigderson |
Public-key cryptography from different assumptions. |
STOC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Avi Wigderson |
Algebrization: A New Barrier in Complexity Theory. |
TOCT |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
New Direct-Product Testers and 2-Query PCPs. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Zeev Dvir, Avi Wigderson |
Monotone expanders - constructions and applications. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Avi Wigderson |
Linear systems over composite moduli. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Emanuele Viola, Avi Wigderson |
One-way multiparty communication lower bound for pointer jumping with applications. |
Combinatorica |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Ariel Gabizon, Avi Wigderson |
Extractors And Rank Extractors For Polynomial Sources. |
Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
Derandomization, Extractors |
| 1 | Sanjeev Arora, David Steurer, Avi Wigderson |
Towards a Study of Low-Complexity Graphs. |
ICALP |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Avi Wigderson |
Linear Systems over Composite Moduli. |
FOCS |
2009 |
DBLP DOI BibTeX RDF |
Boolean circuit complexity, modular gates, matrix rigidity, exponential sums, constant-depth circuits |
| 1 | Avi Wigderson |
Randomness extractors -- applications and constructions. |
FSTTCS |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
New direct-product testers and 2-query PCPs. |
STOC |
2009 |
DBLP DOI BibTeX RDF |
testing, PCP, parallel repetition, direct products |
| 1 | Avi Wigderson |
The work of Leslie Valiant. |
STOC |
2009 |
DBLP DOI BibTeX RDF |
computational complexity, parallel computing, learning theory, cognitive theory, holographic algorithms |
| 1 | Zeev Dvir, Avi Wigderson |
Kakeya sets, new mergers and old extractors. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson |
Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Scott Aaronson, Avi Wigderson |
Algebrization: A New Barrier in Complexity Theory. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Avi Wigderson, David Xiao |
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. |
Theory of Computing |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola, Avi Wigderson |
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. |
Theory of Computing |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Avi Wigderson |
Public Key Cryptography from Different Assumptions. |
IACR Cryptology ePrint Archive |
2008 |
DBLP BibTeX RDF |
|
| 1 | Gil Kalai, Avi Wigderson |
Neighborly Embedded Manifolds. |
Discrete & Computational Geometry |
2008 |
DBLP DOI BibTeX RDF |
Neighborliness, Cyclic polytopes, Continuous hashing, Polytopes, Convex bodies |
| 1 | Avi Wigderson |
Randomness - A Computational Complexity Perspective. |
CSR |
2008 |
DBLP DOI BibTeX RDF |
derandomnization, complexity, randomness, pseudorandom |
| 1 | Venkatesan Guruswami, James R. Lee, Avi Wigderson |
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Avi Wigderson |
Kakeya Sets, New Mergers and Old Extractors. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson |
Spherical Cubes and Rounding in High Dimensions. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson |
Uniform direct product theorems: simplified, optimized, and derandomized. |
STOC |
2008 |
DBLP DOI BibTeX RDF |
direct product code, xor code, direct product theorem |
| 1 | Scott Aaronson, Avi Wigderson |
Algebrization: a new barrier in complexity theory. |
STOC |
2008 |
DBLP DOI BibTeX RDF |
communication complexity, oracles, arithmetization, interactive proofs, query complexity, low-degree polynomials |
| 1 | Zeev Dvir, Ariel Gabizon, Avi Wigderson |
Extractors and Rank Extractors for Polynomial Sources. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Emanuele Viola, Avi Wigderson |
One-way multi-party communication lower bound for pointer jumping with applications. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Johan Håstad, Avi Wigderson |
The Randomized Communication Complexity of Set Disjointness. |
Theory of Computing |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Ariel Gabizon, Avi Wigderson |
Extractors and Rank Extractors for Polynomial Sources. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola, Avi Wigderson |
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola, Avi Wigderson |
Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Avi Wigderson, David Xiao |
Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Irit Dinur, Madhu Sudan, Avi Wigderson |
Robust Local Testability of Tensor Products of LDPC Codes. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Eyal Rozenman, Aner Shalev, Avi Wigderson |
Iterative Construction of Cayley Expander Graphs. |
Theory of Computing |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson |
Reducing The Seed Length In The Nisan-Wigderson Generator. |
Combinatorica |
2006 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000): 68Q15 |
| 1 | Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson |
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. |
Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
06D15, 68Q17, 68Q15, 06E30, Subject classification. 68Q10 |
| 1 | Boaz Barak, Russell Impagliazzo, Avi Wigderson |
Extracting Randomness Using Few Independent Sources. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Shpilka, Avi Wigderson |
Derandomizing Homomorphism Testing in General Groups. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Omer Reingold, Ronen Shaltiel, Avi Wigderson |
Extracting Randomness via Repeated Condensing. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Avi Wigderson |
The Power and Weakness of Randomness in Computation. |
LATIN |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Madhu Sudan, Avi Wigderson |
Robust Local Testability of Tensor Products of LDPC Codes. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Avi Wigderson |
Applications of the Sum-Product Theorem in Finite Fields. |
IEEE Conference on Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson |
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. |
STOC |
2006 |
DBLP DOI BibTeX RDF |
independent sources, extractors, dispersers, Ramsey graphs |
| 1 | Avi Wigderson, David Xiao |
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Michael Luby, Avi Wigderson |
Pairwise Independence and Derandomization. |
Foundations and Trends in Theoretical Computer Science |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Avi Wigderson, David Xiao |
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. |
FOCS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson |
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. |
IEEE Conference on Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson |
Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
dispersers condenser, constructions, extractors, explicit, ramsey graphs |
| 1 | Roy Meshulam, Avi Wigderson |
Expanders In Group Algebras. |
Combinatorica |
2004 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000): 05C25, 20C15 |
| 1 | Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson |
Near Optimal Separation Of Tree-Like And General Resolution. |
Combinatorica |
2004 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000): 03F20, 68Q17 |
| 1 | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
Pseudorandom Generators in Propositional Proof Complexity. |
SIAM J. Comput. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Russell Impagliazzo, Avi Wigderson |
Extracting Randomness Using Few Independent Sources. |
FOCS |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Shpilka, Avi Wigderson |
Derandomizing homomorphism testing in general groups. |
STOC |
2004 |
DBLP DOI BibTeX RDF |
homomorphism testing, derandomization, linearity testing |
| 1 | Eyal Rozenman, Aner Shalev, Avi Wigderson |
A new family of Cayley expanders (?). |
STOC |
2004 |
DBLP DOI BibTeX RDF |
zig-zag product, Cayley graphs, expanders |
| 1 | Avi Wigderson |
Depth through breadth, or why should we attend talks in other areas? |
STOC |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad, Avi Wigderson |
Simple analysis of graph tests for linearity and PCP. |
Random Struct. Algorithms |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson |
The Quantum Communication Complexity of Sampling. |
SIAM J. Comput. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Ronen Shaltiel, Avi Wigderson |
Computational Analogues of Entropy. |
RANDOM-APPROX |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Avi Wigderson |
Zigzag Products, Expander Constructions, Connections, and Applications. |
FSTTCS |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson |
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. |
STOC |
2003 |
DBLP DOI BibTeX RDF |
property testing, probabilistically checkable proofs, locally testable codes, linearity testing, low degree testing |
| 1 | Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
Extractors: optimal up to constant factors. |
STOC |
2003 |
DBLP DOI BibTeX RDF |
locally decodable error-correcting codes, pseudorandomness, condensers, randomness extractors, mergers |
| 1 | Oded Goldreich, Avi Wigderson |
Derandomization that is rarely wrong from short advice that is typically good |
Electronic Colloquium on Computational Complexity (ECCC) |
2002 |
DBLP BibTeX RDF |
|
| 1 | Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao |
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. |
Combinatorica |
2002 |
DBLP DOI BibTeX RDF |
AMS Subject Classification (2000): 03F20, 68Q17 |
| 1 | Oded Goldreich, Salil P. Vadhan, Avi Wigderson |
On interactive proofs with a laconic prover. |
Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
Mathematics Subject Classification (2000). 68Q05, 91A05, 68Q15, 68Q10 |
| 1 | Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
In search of an easy witness: exponential time vs. probabilistic polynomial time. |
J. Comput. Syst. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
Space Complexity in Propositional Calculus. |
SIAM J. Comput. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Avi Wigderson |
Derandomization That Is Rarely Wrong from Short Advice That Is Typically Good. |
RANDOM |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Ehud Friedgut, Jeff Kahn, Avi Wigderson |
Computing Graph Properties by Randomized Subcube Partitions. |
RANDOM |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Roy Meshulam, Avi Wigderson |
Expanders from Symmetric Codes. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
Randomness Conductors and Constant-Degree Lossless Expanders. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
expander graphs, extractors, condensers, graph products |
| 1 | Roy Meshulam, Avi Wigderson |
Expanders from symmetric codes. |
STOC |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
Randomness conductors and constant-degree lossless expanders. |
STOC |
2002 |
DBLP DOI BibTeX RDF |
expander graphs, extractors, condensers, graph products |
| 1 | Oded Goldreich, Salil P. Vadhan, Avi Wigderson |
On Interactive Proofs with a Laconic Prover |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Omer Reingold, Salil P. Vadhan, Avi Wigderson |
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Avi Wigderson |
Short proofs are narrow - resolution made simple. |
J. ACM |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Shpilka, Avi Wigderson |
Depth-3 arithmetic circuits over fields of characteristic zero. |
Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Avi Wigderson |
Randomness vs Time: Derandomization under a Uniform Assumption. |
J. Comput. Syst. Sci. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Salil P. Vadhan, Avi Wigderson |
On Interactive Proofs with a Laconic Prover. |
ICALP |
2001 |
DBLP DOI BibTeX RDF |
sampling protocols, statistical zero knowledge, game theory, interactive proofs, Arthur-Merlin games |
| 1 | Noga Alon, Alexander Lubotzky, Avi Wigderson |
Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. |
FOCS |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time. (PDF / PS) |
IEEE Conference on Computational Complexity |
2001 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")