Travelled to:10 × USA
2 × Greece
Collaborated with:∅ A.Samorodnitsky S.P.Vadhan S.O.Gharan J.Katz J.R.Lee G.Schoenebeck M.Tulsiani O.Reingold L.Fortnow R.Santhanam B.Chazelle R.Rubinfeld M.Sudan T.C.Kwok L.C.Lau Y.T.Lee
Talks about:spectral (3) approxim (3) pseudorandom (2) uniform (2) problem (2) generat (2) cheeger (2) partit (2) higher (2) queri (2)
Person: Luca Trevisan
DBLP: Trevisan:Luca
Contributed to:
201320122009200720062005
200120012000199919981997Wrote 16 papers:
- STOC-2013-KwokLLGT #algorithm #analysis #clustering #difference #higher-order
- Improved Cheeger’s inequality: analysis of spectral partitioning algorithms through higher order spectral gap (TCK, LCL, YTL, SOG, LT), pp. 11–20.
- STOC-2012-LeeGT #clustering #higher-order #multi
- Multi-way spectral partitioning and higher-order cheeger inequalities (JRL, SOG, LT), pp. 1117–1130.
- STOC-2009-Trevisan
- Max cut and the smallest eigenvalue (LT), pp. 263–272.
- STOC-2007-SchoenebeckTT
- Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut (GS, LT, MT), pp. 302–310.
- STOC-2006-ReingoldTV #graph #problem #pseudo
- Pseudorandom walks on regular digraphs and the RL vs. L problem (OR, LT, SPV), pp. 457–466.
- STOC-2006-SamorodnitskyT
- Gowers uniformity, influence of variables, and PCPs (AS, LT), pp. 11–20.
- STOC-2005-FortnowST #semantics
- Hierarchies for semantic classes (LF, RS, LT), pp. 348–355.
- STOC-2005-Trevisan #on the
- On uniform amplification of hardness in NP (LT), pp. 31–38.
- ICALP-2001-ChazelleRT #approximate #sublinear
- Approximating the Minimum Spanning Tree Weight in Sublinear Time (BC, RR, LT), pp. 190–200.
- STOC-2001-Trevisan #bound #optimisation #problem
- Non-approximability results for optimization problems on bounded degree instances (LT), pp. 453–461.
- STOC-2000-KatzT #on the #performance
- On the efficiency of local decoding procedures for error-correcting codes (JK, LT), pp. 80–86.
- STOC-2000-SamorodnitskyT #complexity #query
- A PCP characterization of NP with optimal amortized query complexity (AS, LT), pp. 191–199.
- STOC-1999-SudanTV #generative #pseudo
- Pseudorandom Generators Without the XOR Lemma (MS, LT, SPV), pp. 537–546.
- STOC-1999-Trevisan #generative #pseudo #using
- Construction of Extractors Using Pseudo-Random Generators (LT), pp. 141–148.
- STOC-1998-Trevisan #query #testing
- Recycling Queries in PCPs and in Linearity Tests (LT), pp. 299–308.
- STOC-1997-Trevisan #geometry
- When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (LT), pp. 21–29.