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