| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Luca Trevisan |
Pseudorandomness and derandomization.  |
ACM Crossroads  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Shayan Oveis Gharan, Luca Trevisan |
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering |
CoRR |
2012 |
DBLP BibTeX RDF |
|
| 1 | James R. Lee, Shayan Oveis Gharan, Luca Trevisan |
Multi-way spectral partitioning and higher-order cheeger inequalities. |
STOC |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan |
Information Spreading in Dynamic Graphs |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Shayan Oveis Gharan, Luca Trevisan |
A Higher-Order Cheeger's Inequality |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | James R. Lee, Shayan Oveis Gharan, Luca Trevisan |
Multi-way spectral partitioning and higher-order Cheeger inequalities |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich, Madhu Sudan, Luca Trevisan |
From Logarithmic Advice to Single-Bit Advice. |
Studies in Complexity and Cryptography |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Dense Model Theorems and Their Applications. |
TCC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
The Program-Enumeration Bottleneck in Average-Case Complexity Theory. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Anindya De, Luca Trevisan, Madhur Tulsiani |
Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. |
CRYPTO |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani |
Improved Pseudorandom Generators for Depth 2 Circuits. |
APPROX-RANDOM |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
The Program-Enumeration Bottleneck in Average-Case Complexity Theory. |
IEEE Conference on Computational Complexity |
2010 |
DBLP DOI BibTeX RDF |
Universal Search, Average-case Complexity |
| 1 | Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani |
Improved Pseudorandom Generators for Depth 2 Circuits. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Anindya De, Luca Trevisan, Madhur Tulsiani |
Non-uniform attacks against one-way functions and PRGs. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Chandra Chekuri, Luca Trevisan |
Foreword. |
Algorithmica |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Guest column: additive combinatorics and theoretical computer science. |
SIGACT News |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Alex Samorodnitsky, Luca Trevisan |
Gowers Uniformity, Influence of Variables, and PCPs. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | James Cook, Omid Etesami, Rachel Miller, Luca Trevisan |
Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms. |
TCC |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Luca Trevisan |
Extractors Using Hardness Amplification. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
Extractors, Direct product theorems, Hardness amplification |
| 1 | Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan |
Pseudorandom Bit Generators That Fool Modular Sums. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. |
IEEE Conference on Computational Complexity |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Max cut and the smallest eigenvalue. |
STOC |
2009 |
DBLP DOI BibTeX RDF |
maximum cut, spectral partitioning |
| 1 | Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
Dense Subsets of Pseudorandom Sets. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Approximation Algorithms for Unique Games. |
Theory of Computing |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Max Cut and the Smallest Eigenvalue |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Learning Heavy Fourier Coefficients of Boolean Functions. |
Encyclopedia of Algorithms |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
Dense Subsets of Pseudorandom Sets. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Average-case Complexity. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan, Salil P. Vadhan |
Pseudorandomness and Average-Case Complexity Via Uniform Reductions. |
Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
Subject classification, 68Q10 |
| 1 | Luca Trevisan |
Fun with Sub-linear Time Algorithms. |
FUN |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee |
Amplifying Collision Resistance: A Complexity-Theoretic Treatment. |
CRYPTO |
2007 |
DBLP DOI BibTeX RDF |
hash functions, combiners, collision resistance, hardness amplification |
| 1 | Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |
Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. |
STOC |
2007 |
DBLP DOI BibTeX RDF |
Lovasz-Schrijver hierarchy, approximation algorithms, linear programming, integrality gap |
| 1 | Andrej Bogdanov, Luca Trevisan |
Average-Case Complexity. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Pseudorandomness and Combinatorial Constructions |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Elchanan Mossel, Amir Shpilka, Luca Trevisan |
On epsilon-biased generators in NC0. |
Random Struct. Algorithms |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Luca Trevisan |
Average-Case Complexity. |
Foundations and Trends in Theoretical Computer Science |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan |
Lower bounds for linear locally decodable codes and private information retrieval. |
Computational Complexity |
2006 |
DBLP DOI BibTeX RDF |
Subject classification, 68P30 |
| 1 | Andrej Bogdanov, Luca Trevisan |
Average-Case Complexity |
CoRR |
2006 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Pseudorandomness and Combinatorial Constructions |
CoRR |
2006 |
DBLP BibTeX RDF |
|
| 1 | Andrej Bogdanov, Luca Trevisan |
On Worst-Case to Average-Case Reductions for NP Problems. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Omer Reingold, Luca Trevisan, Salil P. Vadhan |
Pseudorandom walks on regular digraphs and the RL vs. L problem. |
STOC |
2006 |
DBLP DOI BibTeX RDF |
universal traversal sequence, zig-zag product, derandomization, expander graphs, mixing time, space-bounded computation |
| 1 | Alex Samorodnitsky, Luca Trevisan |
Gowers uniformity, influence of variables, and PCPs. |
STOC |
2006 |
DBLP DOI BibTeX RDF |
influence of variables, probabilistically checkable proofs, linearity test |
| 1 | Luca Trevisan |
Approximation Algorithms for Unique Games |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Omer Reingold, Luca Trevisan, Salil P. Vadhan |
Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan, Salil P. Vadhan, David Zuckerman |
Compression of Samplable Sources |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Andrej Bogdanov, Luca Trevisan |
On Worst-Case to Average-Case Reductions for NP Problems |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Alex Samorodnitsky, Luca Trevisan |
Gowers Uniformity, Influence of Variables, and PCPs |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Maria J. Serna, Luca Trevisan, Fatos Xhafa |
The approximability of non-Boolean satisfiability problems and restricted integer programming. |
Theor. Comput. Sci. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Schallhart, Luca Trevisan |
Approximating Succinct MaxSat. |
J. Log. Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan, Salil P. Vadhan, David Zuckerman |
Compression of Samplable Sources. |
Computational Complexity |
2005 |
DBLP DOI BibTeX RDF |
Subject classification, 68P30 |
| 1 | Alex Samorodnitsky, Luca Trevisan |
Gowers Uniformity, Influence of Variables, and PCPs |
CoRR |
2005 |
DBLP BibTeX RDF |
|
| 1 | Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan |
Approximating the Minimum Spanning Tree Weight in Sublinear Time. |
SIAM J. Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Rosario Gennaro, Yael Gertner, Jonathan Katz, Luca Trevisan |
Bounds on the Efficiency of Generic Cryptographic Constructions. |
SIAM J. Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Henry C. Lin, Luca Trevisan, Hoeteck Wee |
On Hardness Amplification of One-Way Functions. |
TCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Klaus Jansen, José D. P. Rolim, Luca Trevisan (eds.) |
Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings |
APPROX-RANDOM |
2005 |
DBLP BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Luca Trevisan |
The Complexity of Making Unique Choices: Approximating 1-in- k SAT. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Approximation Algorithms for Unique Games. |
FOCS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
On uniform amplification of hardness in NP. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
amplification of hardness, average-case complexity |
| 1 | Lance Fortnow, Rahul Santhanam, Luca Trevisan |
Hierarchies for semantic classes. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
hierarchy theorems, semantic classes, advice |
| 1 | Lance Fortnow, Rahul Santhanam, Luca Trevisan |
Promise Hierarchies |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Inapproximability of Combinatorial Optimization Problems |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Some Applications of Coding Theory in Computational Complexity |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich, Madhu Sudan, Luca Trevisan |
From logarithmic advice to single-bit advice |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Inapproximability of Combinatorial Optimization Problems |
CoRR |
2004 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Some Applications of Coding Theory in Computational Complexity |
CoRR |
2004 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
On Local Versus Global Satisfiability. |
SIAM J. Discrete Math. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Cynthia Dwork, Ronen Shaltiel, Adam Smith, Luca Trevisan |
List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument. |
TCC |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Omer Reingold, Luca Trevisan, Salil P. Vadhan |
Notions of Reducibility between Cryptographic Primitives. |
TCC |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
A Note on Approximate Counting for k-DNF. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan, Salil P. Vadhan, David Zuckerman |
Compression of Samplable Sources. |
IEEE Conference on Computational Complexity |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Luca Trevisan |
Lower Bounds for Testing Bipartiteness in Dense Graphs. |
IEEE Conference on Computational Complexity |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
List Decoding Using the XOR Lemma |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Elchanan Mossel, Amir Shpilka, Luca Trevisan |
On epsilon-Biased Generators in NC0 |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
An epsilon-Biased Generator in NC0 |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich, Luca Trevisan |
Three theorems regarding testing graph properties. |
Random Struct. Algorithms |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Luca Trevisan |
On Worst-Case to Average-Case Reductions for NP Problems. |
FOCS |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
List-Decoding Using The XOR Lemma. |
FOCS |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Elchanan Mossel, Amir Shpilka, Luca Trevisan |
On e-Biased Generators in NC0. |
FOCS |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Error-Correcting Codes in Complexity Theory. |
CIAC |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
A Note on Deterministic Approximate Counting for k-DNF |
Electronic Colloquium on Computational Complexity (ECCC) |
2002 |
DBLP BibTeX RDF |
|
| 1 | Andrej Bogdanov, Luca Trevisan |
Lower Bounds for Testing Bipartiteness in Dense Graphs |
Electronic Colloquium on Computational Complexity (ECCC) |
2002 |
DBLP BibTeX RDF |
|
| 1 | Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan |
Counting Distinct Elements in a Data Stream. |
RANDOM |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Kenji Obata, Luca Trevisan |
A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. |
FOCS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan, Salil P. Vadhan |
Pseudorandomness and Average-Case Complexity via Uniform Reductions. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel |
Streaming Computation of Combinatorial Objects. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
error-correcting codes, extractors, dispersers, streaming computation, universal hash functions, online computation |
| 1 | Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan |
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
Error Correcting Codes, Linear Codes, Private Information Retrieval |
| 1 | Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan |
Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Oded Goldreich, Luca Trevisan |
Three Theorems regarding Testing Graph Properties. |
Electronic Colloquium on Computational Complexity (ECCC) |
2001 |
DBLP BibTeX RDF |
|
| 1 | Josep Díaz, Jordi Petit, Maria J. Serna, Luca Trevisan |
Approximating layout problems on random graphs. |
Discrete Mathematics |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Pierluigi Crescenzi, Riccardo Silvestri, Luca Trevisan |
On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. |
Inf. Comput. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Trevisan |
Extractors and pseudorandom generators. |
J. ACM |
2001 |
DBLP DOI BibTeX RDF |
Error-correcting codes, extractors, pseudorandomness |
| 1 | Madhu Sudan, Luca Trevisan, Salil P. Vadhan |
Pseudorandom Generators without the XOR Lemma. |
J. Comput. Syst. Sci. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan |
Approximating the Minimum Spanning Tree Weight in Sublinear Time. |
ICALP |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Michel X. Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan (eds.) |
Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18-20, 2001, Proceedings |
RANDOM-APPROX |
2001 |
DBLP BibTeX RDF |
|
| 1 | Luca Trevisan |
Error-Correcting Codes and Pseudorandom Projections. |
RANDOM-APPROX |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich, Luca Trevisan |
Three Theorems Regarding Testing Graph Properties. |
FOCS |
2001 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")