The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Luca Trevisan: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. Venkatesan Guruswami, Luca Trevisan
    The Complexity of Making Unique Choices: Approximating 1-in- k SAT. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2005, pp:99-110 [Conf]
  2. Luca Trevisan
    A Note on Approximate Counting for k-DNF. [Citation Graph (0, 0)][DBLP]
    APPROX-RANDOM, 2004, pp:417-426 [Conf]
  3. Luca Trevisan
    Error-Correcting Codes in Complexity Theory. [Citation Graph (0, 0)][DBLP]
    CIAC, 2003, pp:4- [Conf]
  4. Andrej Bogdanov, Luca Trevisan
    Lower Bounds for Testing Bipartiteness in Dense Graphs. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2004, pp:75-81 [Conf]
  5. Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel
    Streaming Computation of Combinatorial Objects. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2002, pp:165-174 [Conf]
  6. Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
    Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2002, pp:175-183 [Conf]
  7. Sanjeev Khanna, Madhu Sudan, Luca Trevisan
    Constraint Satisfaction: The Approximability of Minimization Problems. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1997, pp:282-296 [Conf]
  8. Madhu Sudan, Luca Trevisan, Salil P. Vadhan
    Pseudorandom Generators without the XOR Lemma (Abstract). [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 1999, pp:4- [Conf]
  9. Luca Trevisan
    A Survey of Optimal PCP Characterizations of NP. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2000, pp:146-0 [Conf]
  10. Luca Trevisan, Salil P. Vadhan
    Pseudorandomness and Average-Case Complexity via Uniform Reductions. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2002, pp:129-138 [Conf]
  11. Luca Trevisan, Salil P. Vadhan, David Zuckerman
    Compression of Samplable Sources. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2004, pp:1-14 [Conf]
  12. Andrea E. F. Clementi, Luca Trevisan
    Improved Non-approximability Results for Vertex Cover with Density Constraints. [Citation Graph (0, 0)][DBLP]
    COCOON, 1996, pp:333-342 [Conf]
  13. Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan
    Structure in Approximation Classes (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    COCOON, 1995, pp:539-548 [Conf]
  14. Luca Trevisan
    Positive Linear Programming, Parallel Approximation and PCP's. [Citation Graph (0, 0)][DBLP]
    ESA, 1996, pp:62-75 [Conf]
  15. Luca Trevisan
    Approximating Satisfiable Satisfiability Problems (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    ESA, 1997, pp:472-485 [Conf]
  16. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan
    Weak Random Sources, Hitting Sets, and BPP Simulations. [Citation Graph (0, 0)][DBLP]
    FOCS, 1997, pp:264-272 [Conf]
  17. Andrej Bogdanov, Kenji Obata, Luca Trevisan
    A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. [Citation Graph (0, 0)][DBLP]
    FOCS, 2002, pp:93-102 [Conf]
  18. Andrej Bogdanov, Luca Trevisan
    On Worst-Case to Average-Case Reductions for NP Problems. [Citation Graph (0, 0)][DBLP]
    FOCS, 2003, pp:308-317 [Conf]
  19. Oded Goldreich, Luca Trevisan
    Three Theorems Regarding Testing Graph Properties. [Citation Graph (0, 0)][DBLP]
    FOCS, 2001, pp:460-469 [Conf]
  20. Rosario Gennaro, Luca Trevisan
    Lower Bounds on the Efficiency of Generic Cryptographic Constructions. [Citation Graph (0, 0)][DBLP]
    FOCS, 2000, pp:305-313 [Conf]
  21. Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
    A Tight Characterization of NP with 3 Query PCPs. [Citation Graph (0, 0)][DBLP]
    FOCS, 1998, pp:8-17 [Conf]
  22. Elchanan Mossel, Amir Shpilka, Luca Trevisan
    On e-Biased Generators in NC0. [Citation Graph (0, 0)][DBLP]
    FOCS, 2003, pp:136-145 [Conf]
  23. Madhu Sudan, Luca Trevisan
    Probabilistically Checkable Proofs with Low Amortized Query Complexity. [Citation Graph (0, 0)][DBLP]
    FOCS, 1998, pp:18-27 [Conf]
  24. Luca Trevisan
    List-Decoding Using The XOR Lemma. [Citation Graph (0, 0)][DBLP]
    FOCS, 2003, pp:126-135 [Conf]
  25. Luca Trevisan
    Approximation Algorithms for Unique Games. [Citation Graph (0, 0)][DBLP]
    FOCS, 2005, pp:197-205 [Conf]
  26. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
    Gadgets, Approximation, and Linear Programming (extended abstract). [Citation Graph (0, 0)][DBLP]
    FOCS, 1996, pp:617-626 [Conf]
  27. Luca Trevisan, Salil P. Vadhan
    Extracting Randomness from Samplable Distributions. [Citation Graph (0, 0)][DBLP]
    FOCS, 2000, pp:32-42 [Conf]
  28. Michele Boreale, Luca Trevisan
    On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    FSTTCS, 1995, pp:294-308 [Conf]
  29. Pierluigi Crescenzi, Luca Trevisan
    On Approximation Scheme Preserving Reducability and Its Applications. [Citation Graph (0, 0)][DBLP]
    FSTTCS, 1994, pp:330-341 [Conf]
  30. Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan
    Approximating the Minimum Spanning Tree Weight in Sublinear Time. [Citation Graph (0, 0)][DBLP]
    ICALP, 2001, pp:190-200 [Conf]
  31. Pierluigi Crescenzi, Riccardo Silvestri, Luca Trevisan
    To Weight or Not to Weight: Where is the Question? [Citation Graph (0, 0)][DBLP]
    ISTCS, 1996, pp:68-77 [Conf]
  32. Michele Boreale, Luca Trevisan
    Bisimilarity Problems Requiring Exponential Time. [Citation Graph (0, 0)][DBLP]
    MFCS, 1996, pp:230-241 [Conf]
  33. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan
    Counting Distinct Elements in a Data Stream. [Citation Graph (0, 0)][DBLP]
    RANDOM, 2002, pp:1-10 [Conf]
  34. Luca Trevisan
    Error-Correcting Codes and Pseudorandom Projections. [Citation Graph (0, 0)][DBLP]
    RANDOM-APPROX, 2001, pp:7-9 [Conf]
  35. Maria J. Serna, Luca Trevisan, Fatos Xhafa
    The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. [Citation Graph (0, 0)][DBLP]
    STACS, 1998, pp:488-498 [Conf]
  36. Lance Fortnow, Rahul Santhanam, Luca Trevisan
    Hierarchies for semantic classes. [Citation Graph (0, 0)][DBLP]
    STOC, 2005, pp:348-355 [Conf]
  37. Jonathan Katz, Luca Trevisan
    On the efficiency of local decoding procedures for error-correcting codes. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:80-86 [Conf]
  38. Omer Reingold, Luca Trevisan, Salil P. Vadhan
    Pseudorandom walks on regular digraphs and the RL vs. L problem. [Citation Graph (0, 0)][DBLP]
    STOC, 2006, pp:457-466 [Conf]
  39. Alex Samorodnitsky, Luca Trevisan
    A PCP characterization of NP with optimal amortized query complexity. [Citation Graph (0, 0)][DBLP]
    STOC, 2000, pp:191-199 [Conf]
  40. Alex Samorodnitsky, Luca Trevisan
    Gowers uniformity, influence of variables, and PCPs. [Citation Graph (0, 0)][DBLP]
    STOC, 2006, pp:11-20 [Conf]
  41. Madhu Sudan, Luca Trevisan, Salil P. Vadhan
    Pseudorandom Generators Without the XOR Lemma (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1999, pp:537-546 [Conf]
  42. Luca Trevisan
    Non-approximability results for optimization problems on bounded degree instances. [Citation Graph (0, 0)][DBLP]
    STOC, 2001, pp:453-461 [Conf]
  43. Luca Trevisan
    On uniform amplification of hardness in NP. [Citation Graph (0, 0)][DBLP]
    STOC, 2005, pp:31-38 [Conf]
  44. Luca Trevisan
    When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1997, pp:21-29 [Conf]
  45. Luca Trevisan
    Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1998, pp:299-308 [Conf]
  46. Luca Trevisan
    Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    STOC, 1999, pp:141-148 [Conf]
  47. Henry Lin, Luca Trevisan, Hoeteck Wee
    On Hardness Amplification of One-Way Functions. [Citation Graph (0, 0)][DBLP]
    TCC, 2005, pp:34-49 [Conf]
  48. Omer Reingold, Luca Trevisan, Salil P. Vadhan
    Notions of Reducibility between Cryptographic Primitives. [Citation Graph (0, 0)][DBLP]
    TCC, 2004, pp:1-20 [Conf]
  49. Cynthia Dwork, Ronen Shaltiel, Adam Smith, Luca Trevisan
    List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument. [Citation Graph (0, 0)][DBLP]
    TCC, 2004, pp:101-120 [Conf]
  50. Pierluigi Crescenzi, Luca Trevisan
    Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract). [Citation Graph (0, 0)][DBLP]
    WG, 1994, pp:130-139 [Conf]
  51. Luca Trevisan
    Erratum: A Correction to ``Parallel Approximation Algorithms by Positive Linear Programming''. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 2000, v:27, n:2, pp:115-119 [Journal]
  52. Luca Trevisan
    Approximating Satisfiable Satisfiability Problems. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 2000, v:28, n:1, pp:145-172 [Journal]
  53. Luca Trevisan
    Parallel Approximation Algorithms by Positive Linear Programming. [Citation Graph (0, 0)][DBLP]
    Algorithmica, 1998, v:21, n:1, pp:72-88 [Journal]
  54. Luca Trevisan
    Interactive and probabilistic proof-checking. [Citation Graph (0, 0)][DBLP]
    Ann. Pure Appl. Logic, 2000, v:104, n:1-3, pp:325-342 [Journal]
  55. Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
    Lower bounds for linear locally decodable codes and private information retrieval. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 2006, v:15, n:3, pp:263-296 [Journal]
  56. Luca Trevisan, Salil P. Vadhan, David Zuckerman
    Compression of Samplable Sources. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 2005, v:14, n:3, pp:186-227 [Journal]
  57. Luca Trevisan
    Inapproximability of Combinatorial Optimization Problems [Citation Graph (0, 0)][DBLP]
    CoRR, 2004, v:0, n:, pp:- [Journal]
  58. Luca Trevisan
    Some Applications of Coding Theory in Computational Complexity [Citation Graph (0, 0)][DBLP]
    CoRR, 2004, v:0, n:, pp:- [Journal]
  59. Josep Díaz, Jordi Petit, Maria J. Serna, Luca Trevisan
    Approximating layout problems on random graphs. [Citation Graph (0, 0)][DBLP]
    Discrete Mathematics, 2001, v:235, n:1-3, pp:245-253 [Journal]
  60. Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan
    Recent Advances Towards Proving P = BPP. [Citation Graph (0, 0)][DBLP]
    Bulletin of the EATCS, 1998, v:64, n:, pp:- [Journal]
  61. Rosario Gennaro, Luca Trevisan
    Lower Bounds on the Efficiency of Generic Cryptographic Constructions [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2000, v:7, n:22, pp:- [Journal]
  62. Oded Goldreich, Luca Trevisan
    Three Theorems regarding Testing Graph Properties. [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:10, pp:- [Journal]
  63. Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
    Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:080, pp:- [Journal]
  64. Luca Trevisan
    A Note on Deterministic Approximate Counting for k-DNF [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2002, v:, n:069, pp:- [Journal]
  65. Luca Trevisan
    An epsilon-Biased Generator in NC0 [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2003, v:10, n:013, pp:- [Journal]
  66. Luca Trevisan
    List Decoding Using the XOR Lemma [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2003, v:, n:042, pp:- [Journal]
  67. Elchanan Mossel, Amir Shpilka, Luca Trevisan
    On epsilon-Biased Generators in NC0 [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2003, v:, n:043, pp:- [Journal]
  68. Luca Trevisan
    Some Applications of Coding Theory in Computational Complexity [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:043, pp:- [Journal]
  69. Luca Trevisan
    Inapproximability of Combinatorial Optimization Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:065, pp:- [Journal]
  70. Oded Goldreich, Madhu Sudan, Luca Trevisan
    From logarithmic advice to single-bit advice [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:093, pp:- [Journal]
  71. Lance Fortnow, Rahul Santhanam, Luca Trevisan
    Promise Hierarchies [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2004, v:, n:098, pp:- [Journal]
  72. Luca Trevisan, Salil P. Vadhan, David Zuckerman
    Compression of Samplable Sources [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:012, pp:- [Journal]
  73. Andrej Bogdanov, Luca Trevisan
    On Worst-Case to Average-Case Reductions for NP Problems [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:015, pp:- [Journal]
  74. Omer Reingold, Luca Trevisan, Salil P. Vadhan
    Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:022, pp:- [Journal]
  75. Luca Trevisan
    Approximation Algorithms for Unique Games [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:034, pp:- [Journal]
  76. Alex Samorodnitsky, Luca Trevisan
    Gowers Uniformity, Influence of Variables, and PCPs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2005, v:, n:116, pp:- [Journal]
  77. Luca Trevisan
    Pseudorandomness and Combinatorial Constructions [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 2006, v:, n:013, pp:- [Journal]
  78. Luca Trevisan
    On the Approximability of the Multi-dimensional Euclidean TSP [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1996, v:3, n:46, pp:- [Journal]
  79. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan
    Weak Random Sources, Hitting Sets, and BPP Simulations [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1997, v:4, n:11, pp:- [Journal]
  80. Luca Trevisan
    On Local versus Global Satisfiability [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1997, v:4, n:12, pp:- [Journal]
  81. Luca Trevisan
    Recycling Queries in PCPs and in Linearity Tests [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:7, pp:- [Journal]
  82. Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
    A tight characterization of NP with 3 query PCPs [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:34, pp:- [Journal]
  83. Madhu Sudan, Luca Trevisan
    Probabilistically checkable proofs with low amortized query complexity [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:40, pp:- [Journal]
  84. Luca Trevisan
    Constructions of Near-Optimal Extractors Using Pseudo-Random Generators [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:55, pp:- [Journal]
  85. Madhu Sudan, Luca Trevisan, Salil P. Vadhan
    Pseudorandom generators without the XOR Lemma [Citation Graph (0, 0)][DBLP]
    Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:74, pp:- [Journal]
  86. Pierluigi Crescenzi, Riccardo Silvestri, Luca Trevisan
    On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. [Citation Graph (0, 0)][DBLP]
    Inf. Comput., 2001, v:167, n:1, pp:10-26 [Journal]
  87. Marco Cesati, Luca Trevisan
    On the Efficiency of Polynomial Time Approximation Schemes. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1997, v:64, n:4, pp:165-171 [Journal]
  88. Luca Trevisan
    A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees. [Citation Graph (0, 0)][DBLP]
    Inf. Process. Lett., 1996, v:57, n:5, pp:231-236 [Journal]
  89. Pierluigi Crescenzi, Luca Trevisan
    On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem. [Citation Graph (0, 0)][DBLP]
    ITA, 1996, v:30, n:5, pp:431-441 [Journal]
  90. Luca Trevisan
    Extractors and pseudorandom generators. [Citation Graph (0, 0)][DBLP]
    J. ACM, 2001, v:48, n:4, pp:860-879 [Journal]
  91. José D. P. Rolim, Luca Trevisan
    A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms. [Citation Graph (0, 0)][DBLP]
    J. Comb. Optim., 1998, v:2, n:3, pp:219-236 [Journal]
  92. Madhu Sudan, Luca Trevisan, Salil P. Vadhan
    Pseudorandom Generators without the XOR Lemma. [Citation Graph (0, 0)][DBLP]
    J. Comput. Syst. Sci., 2001, v:62, n:2, pp:236-266 [Journal]
  93. Christian Schallhart, Luca Trevisan
    Approximating Succinct MaxSat. [Citation Graph (0, 0)][DBLP]
    J. Log. Comput., 2005, v:15, n:4, pp:551-557 [Journal]
  94. Pierluigi Crescenzi, Luca Trevisan
    On Approximation Scheme Preserving Reducibility and Its Applications. [Citation Graph (0, 0)][DBLP]
    Theory Comput. Syst., 2000, v:33, n:1, pp:1-16 [Journal]
  95. Luca Trevisan, Fatos Xhafa
    The Parallel Complexity of Positive Linear Programming. [Citation Graph (0, 0)][DBLP]
    Parallel Processing Letters, 1998, v:8, n:4, pp:527-533 [Journal]
  96. Oded Goldreich, Luca Trevisan
    Three theorems regarding testing graph properties. [Citation Graph (0, 0)][DBLP]
    Random Struct. Algorithms, 2003, v:23, n:1, pp:23-57 [Journal]
  97. Elchanan Mossel, Amir Shpilka, Luca Trevisan
    On epsilon-biased generators in NC0. [Citation Graph (0, 0)][DBLP]
    Random Struct. Algorithms, 2006, v:29, n:1, pp:56-81 [Journal]
  98. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan
    Weak Random Sources, Hitting Sets, and BPP Simulations. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1999, v:28, n:6, pp:2103-2116 [Journal]
  99. Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan
    Structure in Approximation Classes. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 1999, v:28, n:5, pp:1759-1782 [Journal]
  100. Rosario Gennaro, Yael Gertner, Jonathan Katz, Luca Trevisan
    Bounds on the Efficiency of Generic Cryptographic Constructions. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2005, v:35, n:1, pp:217-246 [Journal]
  101. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson
    The Approximability of Constraint Satisfaction Problems. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2000, v:30, n:6, pp:1863-1920 [Journal]
  102. Luca Trevisan
    When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2000, v:30, n:2, pp:475-485 [Journal]
  103. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
    Gadgets, Approximation, and Linear Programming. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2000, v:29, n:6, pp:2074-2097 [Journal]
  104. Andrej Bogdanov, Luca Trevisan
    On Worst-Case to Average-Case Reductions for NP Problems. [Citation Graph (0, 0)][DBLP]
    SIAM J. Comput., 2006, v:36, n:4, pp:1119-1159 [Journal]
  105. Luca Trevisan
    On Local Versus Global Satisfiability. [Citation Graph (0, 0)][DBLP]
    SIAM J. Discrete Math., 2004, v:17, n:4, pp:541-547 [Journal]
  106. Michele Boreale, Luca Trevisan
    A complexity analysis of bisimilarity for value-passing processes. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2000, v:238, n:1-2, pp:313-345 [Journal]
  107. Andrea E. F. Clementi, Luca Trevisan
    Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1999, v:225, n:1-2, pp:113-128 [Journal]
  108. Pierluigi Crescenzi, Luca Trevisan
    Max NP-completeness Made Easy. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 1999, v:225, n:1-2, pp:65-79 [Journal]
  109. Maria J. Serna, Luca Trevisan, Fatos Xhafa
    The approximability of non-Boolean satisfiability problems and restricted integer programming. [Citation Graph (0, 0)][DBLP]
    Theor. Comput. Sci., 2005, v:332, n:1-3, pp:123-139 [Journal]
  110. Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
    A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. [Citation Graph (0, 0)][DBLP]
    IEEE Conference on Computational Complexity, 2007, pp:205-216 [Conf]
  111. Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee
    Amplifying Collision Resistance: A Complexity-Theoretic Treatment. [Citation Graph (0, 0)][DBLP]
    CRYPTO, 2007, pp:264-283 [Conf]
  112. Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
    Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. [Citation Graph (0, 0)][DBLP]
    STOC, 2007, pp:302-310 [Conf]
  113. Luca Trevisan
    Fun with Sub-linear Time Algorithms. [Citation Graph (0, 0)][DBLP]
    FUN, 2007, pp:15- [Conf]
  114. Luca Trevisan
    Pseudorandomness and Combinatorial Constructions [Citation Graph (0, 0)][DBLP]
    CoRR, 2006, v:0, n:, pp:- [Journal]
  115. Andrej Bogdanov, Luca Trevisan
    Average-Case Complexity [Citation Graph (0, 0)][DBLP]
    CoRR, 2006, v:0, n:, pp:- [Journal]

  116. Extractors Using Hardness Amplification. [Citation Graph (, )][DBLP]


  117. Pseudorandom Bit Generators That Fool Modular Sums. [Citation Graph (, )][DBLP]


  118. Improved Pseudorandom Generators for Depth 2 Circuits. [Citation Graph (, )][DBLP]


  119. Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. [Citation Graph (, )][DBLP]


  120. The Program-Enumeration Bottleneck in Average-Case Complexity Theory. [Citation Graph (, )][DBLP]


  121. Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. [Citation Graph (, )][DBLP]


  122. Average-case Complexity. [Citation Graph (, )][DBLP]


  123. Dense Subsets of Pseudorandom Sets. [Citation Graph (, )][DBLP]


  124. Max cut and the smallest eigenvalue. [Citation Graph (, )][DBLP]


  125. Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms. [Citation Graph (, )][DBLP]


  126. Foreword. [Citation Graph (, )][DBLP]


  127. Pseudorandomness and Average-Case Complexity Via Uniform Reductions. [Citation Graph (, )][DBLP]


  128. Gowers Uniformity, Influence of Variables, and PCPs [Citation Graph (, )][DBLP]


  129. Max Cut and the Smallest Eigenvalue [Citation Graph (, )][DBLP]


  130. Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. [Citation Graph (, )][DBLP]


  131. Dense Subsets of Pseudorandom Sets. [Citation Graph (, )][DBLP]


  132. Average-Case Complexity. [Citation Graph (, )][DBLP]


  133. Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. [Citation Graph (, )][DBLP]


  134. A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. [Citation Graph (, )][DBLP]


Search in 0.031secs, Finished in 0.038secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002