BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
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 DBLP: Trevisan:Luca

Contributed to:

STOC 20132013
STOC 20122012
STOC 20092009
STOC 20072007
STOC 20062006
STOC 20052005
ICALP 20012001
STOC 20012001
STOC 20002000
STOC 19991999
STOC 19981998
STOC 19971997

Wrote 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.
Max cut and the smallest eigenvalue (LT), pp. 263–272.
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.
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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.