Luca Trevisan - RankMe

259 papers A* 51A 21B 10C 2Misc 3Journal 150Unranked 16

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	Recovering Communities in Structured Random Graphs. ITCS Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska
2026	J	`jnl`	Recovering Communities in Structured Random Graphs. CoRR Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska
2024	J	`jnl`	Bond percolation in small-world graphs with power-law distribution. Theor. Comput. Sci. Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
2024	A*	`conf`	New SDP Roundings and Certifiable Approximation for Cubic Optimization. SODA Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan
2024	A*	`conf`	The Minority Dynamics and the Power of Synchronicity. SODA Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, Isabella Ziccardi
2023	A	`conf`	A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. CCC Tommaso d'Orsi, Luca Trevisan
2023	—	`conf`	Bond Percolation in Small-World Graphs with Power-Law Distribution. SAND Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
2023	J	`jnl`	Expansion and flooding in dynamic random networks with node churn. Random Struct. Algorithms Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
2023	J	`jnl`	New SDP Roundings and Certifiable Approximation for Cubic Optimization. CoRR Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan
2023	A*	`conf`	On the Role of Memory in Robust Opinion Dynamics. IJCAI Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, Robin Vacus
2023	J	`jnl`	On the Role of Memory in Robust Opinion Dynamics. CoRR Luca Becchetti, Andrea Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, Robin Vacus
2023	J	`jnl`	The Minority Dynamics and the Power of Synchronicity. CoRR Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, Isabella Ziccardi
2022	J	`jnl`	A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. CoRR Tommaso d'Orsi, Luca Trevisan
2022	J	`jnl`	Bond Percolation in Small-World Graphs with Power-Law Distribution. CoRR Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
2022	A*	`conf`	Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification. SODA Antares Chen, Jonathan Shi, Luca Trevisan
2022	J	`jnl`	Near-Optimal NP-Hardness of Approximating Max k-CSP Theory Comput. Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
2022	J	`jnl`	On the Multidimensional Random Subset Sum Problem. CoRR Luca Becchetti, Arthur Carvalho Walraven da Cunha, Andrea Clementi, Francesco d'Amore, Hicham Lesfari, Emanuele Natale, Luca Trevisan
2022	B	`conf`	Percolation and Epidemic Processes in One-Dimensional Small-World Networks - (Extended Abstract). LATIN Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
2022	A	`conf`	Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models. AISTATS Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, Luca Trevisan
2021	J	`jnl`	Correlation Clustering Reconstruction in Semi-Adversarial Models. CoRR Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, Luca Trevisan
2021	A	`conf`	Expansion and Flooding in Dynamic Random Networks with Node Churn. ICDCS Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
2021	J	`jnl`	Introducing The Theory Blogs Column. Bull. EATCS Luca Trevisan
2021	J	`jnl`	Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming. SIAM J. Discret. Math. Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan
2021	J	`jnl`	Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks. CoRR Luca Becchetti, Andrea Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
2020	A*	`conf`	A New Algorithm for the Robust Semi-random Independent Set Problem. SODA Theo McKenzie, Hermish Mehta, Luca Trevisan
2020	A	`conf`	Consensus vs Broadcast, with and Without Noise (Extended Abstract). ITCS Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, Luca Trevisan
2020	J	`jnl`	Cut Sparsification of the Clique Beyond the Ramanujan Bound. CoRR Antares Chen, Jonathan Shi, Luca Trevisan
2020	J	`jnl`	Expansion and Flooding in Dynamic Random Networks with Node Churn. CoRR Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
2020	J	`jnl`	Find Your Place: Simple Distributed Algorithms for Community Detection. SIAM J. Comput. Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
2020	A*	`conf`	Finding a Bounded-Degree Expander Inside a Dense One. SODA Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
2020	J	`jnl`	From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. SIAM J. Comput. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2020	B	`conf`	Lower Bounds for Max-Cut via Semidefinite Programming. LATIN Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan
2020	A*	`conf`	Subexponential LPs Approximate Max-Cut. FOCS Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
2019	A*	`conf`	New Notions and Constructions of Sparsification for Graphs and Hypergraphs. FOCS Nikhil Bansal, Ola Svensson, Luca Trevisan
2019	J	`jnl`	New Notions and Constructions of Sparsification for Graphs and Hypergraphs. CoRR Nikhil Bansal, Ola Svensson, Luca Trevisan
2019	A*	`conf`	Optimal Lower Bounds for Sketching Graph Cuts. SODA Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan
2019	J	`jnl`	Subexponential LPs Approximate Max-Cut. CoRR Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
2019	J	`jnl`	Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs. CoRR Jess Banks, Luca Trevisan
2018	J	`jnl`	A New Algorithm for the Robust Semi-random Independent Set Problem. CoRR Theo McKenzie, Hermish Mehta, Luca Trevisan
2018	J	`jnl`	A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs. CoRR Charles Carlson, Alexandra Kolla, Luca Trevisan
2018	A*	`conf`	An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification. SODA Nikhil Srivastava, Luca Trevisan
2018	A	`conf`	Average Whenever You Meet: Opportunistic Protocols for Community Detection. ESA Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
2018	J	`jnl`	Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise. CoRR Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, Luca Trevisan
2018	J	`jnl`	Finding a Bounded-Degree Expander Inside a Dense One. CoRR Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
2018	—	`conf`	Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut. APPROX-RANDOM Pasin Manurangsi, Luca Trevisan
2018	J	`jnl`	Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems. CoRR Pasin Manurangsi, Luca Trevisan
2017	J	`jnl`	An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification. CoRR Nikhil Srivastava, Luca Trevisan
2017	A*	`conf`	An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. SODA Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
2017	A*	`conf`	Find Your Place: Simple Distributed Algorithms for Community Detection. SODA Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
2017	J	`jnl`	Friend or Foe? Population Protocols can perform Community Detection. CoRR Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
2017	A*	`conf`	From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017	J	`jnl`	From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. CoRR Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
2017	J	`jnl`	Optimal Lower Bounds for Sketching Graph Cuts. CoRR Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan
2017	J	`jnl`	Simple dynamics for plurality consensus. Distributed Comput. Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan
2016	J	`jnl`	Almost Optimal Local Graph Clustering Using Evolving Sets. J. ACM Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan
2016	J	`jnl`	An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. CoRR Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
2016	A*	`conf`	Approximation of non-boolean 2CSP. SODA Guy Kindler, Alexandra Kolla, Luca Trevisan
2016	—	`ch.`	Learning Heavy Fourier Coefficients of Boolean Functions. Encyclopedia of Algorithms Luca Trevisan
2016	—	`conf`	Near-Optimal UGC-hardness of Approximating Max k-CSP_R. APPROX-RANDOM Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
2016	A*	`conf`	Stabilizing Consensus with Many Opinions. SODA Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
2015	J	`jnl`	A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. Theory Comput. Shayan Oveis Gharan, Luca Trevisan
2015	J	`jnl`	Approximation of non-boolean 2CSP. CoRR Guy Kindler, Alexandra Kolla, Luca Trevisan
2015	—	`conf`	Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Find Your Place: Simple Distributed Algorithms for Community Detection. CoRR Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
2015	J	`jnl`	Information spreading in dynamic graphs. Distributed Comput. Andrea Clementi, Riccardo Silvestri, Luca Trevisan
2015	J	`jnl`	Near-Optimal UGC-hardness of Approximating Max k-CSP_R. CoRR Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
2015	J	`jnl`	Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2015	J	`jnl`	Stabilizing Consensus with Many Opinions. CoRR Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
2015	J	`jnl`	Unique Games on the Hypercube. Chic. J. Theor. Comput. Sci. Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan
2014	J	`jnl`	Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities. J. ACM James R. Lee, Shayan Oveis Gharan, Luca Trevisan
2014	J	`jnl`	On the One-Way Function Candidate Proposed by Goldreich. ACM Trans. Comput. Theory James Cook, Omid Etesami, Rachel Miller, Luca Trevisan
2014	A*	`conf`	Partitioning into Expanders. SODA Shayan Oveis Gharan, Luca Trevisan
2014	J	`jnl`	Quantum lower bound for inverting a permutation with advice. CoRR Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2014	J	`jnl`	Quantum lower bound for inverting a permutation with advice. Electron. Colloquium Comput. Complex. Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2014	B	`conf`	Simple dynamics for plurality consensus. SPAA Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan
2014	J	`jnl`	Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). SIAM J. Comput. Lap Chi Lau, Tal Malkin, Ryan O'Donnell, Luca Trevisan
2014	J	`jnl`	Unique Games on the Hypercube. CoRR Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan
2013	A	`conf`	A Derandomized Switching Lemma and an Improved Derandomization of AC0. CCC Luca Trevisan, Tongke Xue
2013	—	`conf`	A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROX-RANDOM Shayan Oveis Gharan, Luca Trevisan
2013	J	`jnl`	Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank CoRR Shayan Oveis Gharan, Luca Trevisan
2013	J	`jnl`	Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap CoRR Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
2013	A*	`conf`	Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. STOC Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
2013	J	`jnl`	Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut? CoRR Luca Trevisan
2013	J	`jnl`	Partitioning into Expanders. CoRR Shayan Oveis Gharan, Luca Trevisan
2013	J	`jnl`	Simple Dynamics for Majority Consensus. CoRR Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan
2013	C	`ed.`	Theory and Applications of Models of Computation, 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings TAMC T.-H. Hubert Chan, Lap Chi Lau, Luca Trevisan
2012	J	`jnl`	A Derandomized Switching Lemma and an Improved Derandomization of AC0. Electron. Colloquium Comput. Complex. Luca Trevisan
2012	J	`jnl`	A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs CoRR Shayan Oveis Gharan, Luca Trevisan
2012	J	`jnl`	A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues CoRR Shayan Oveis Gharan, Luca Trevisan
2012	J	`jnl`	Approximating the Expansion Profile and Almost Optimal Local Graph Clustering CoRR Shayan Oveis Gharan, Luca Trevisan
2012	A*	`conf`	Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. FOCS Shayan Oveis Gharan, Luca Trevisan
2012	J	`jnl`	Better Pseudorandom Generators from Milder Pseudorandom Restrictions CoRR Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan
2012	A*	`conf`	Better Pseudorandom Generators from Milder Pseudorandom Restrictions. FOCS Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan
2012	J	`jnl`	Better pseudorandom generators from milder pseudorandom restrictions. Electron. Colloquium Comput. Complex. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan
2012	A*	`conf`	Information spreading in dynamic graphs. PODC Andrea Clementi, Riccardo Silvestri, Luca Trevisan
2012	J	`jnl`	Max Cut and the Smallest Eigenvalue. SIAM J. Comput. Luca Trevisan
2012	A*	`conf`	Multi-way spectral partitioning and higher-order cheeger inequalities. STOC James R. Lee, Shayan Oveis Gharan, Luca Trevisan
2012	J	`jnl`	On the One-Way Function Candidate Proposed by Goldreich. Electron. Colloquium Comput. Complex. James Cook, Omid Etesami, Rachel Miller, Luca Trevisan
2012	J	`jnl`	Pseudorandomness and derandomization. XRDS Luca Trevisan
2011	B	`conf`	Dense Model Theorems and Their Applications. TCC Luca Trevisan
2011	—	`ch.`	From Logarithmic Advice to Single-Bit Advice. Studies in Complexity and Cryptography Oded Goldreich, Madhu Sudan, Luca Trevisan
2011	J	`jnl`	Information Spreading in Dynamic Graphs CoRR Andrea Clementi, Riccardo Silvestri, Luca Trevisan
2011	J	`jnl`	Multi-way spectral partitioning and higher-order Cheeger inequalities CoRR James R. Lee, Shayan Oveis Gharan, Luca Trevisan
2010	—	`conf`	Improved Pseudorandom Generators for Depth 2 Circuits. APPROX-RANDOM Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani
2010	A	`conf`	The Program-Enumeration Bottleneck in Average-Case Complexity Theory. CCC Luca Trevisan
2010	J	`jnl`	The Program-Enumeration Bottleneck in Average-Case Complexity Theory. Electron. Colloquium Comput. Complex. Luca Trevisan
2010	A*	`conf`	Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. CRYPTO Anindya De, Luca Trevisan, Madhur Tulsiani
2009	—	`conf`	Extractors Using Hardness Amplification. APPROX-RANDOM Anindya De, Luca Trevisan
2009	J	`jnl`	Foreword. Algorithmica Chandra Chekuri, Luca Trevisan
2009	B	`conf`	Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms. TCC James Cook, Omid Etesami, Rachel Miller, Luca Trevisan
2009	J	`jnl`	Gowers Uniformity, Influence of Variables, and PCPs. SIAM J. Comput. Alex Samorodnitsky, Luca Trevisan
2009	J	`jnl`	Guest column: additive combinatorics and theoretical computer science. SIGACT News Luca Trevisan
2009	J	`jnl`	Improved Pseudorandom Generators for Depth 2 Circuits. Electron. Colloquium Comput. Complex. Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani
2009	A*	`conf`	Max cut and the smallest eigenvalue. STOC Luca Trevisan
2009	J	`jnl`	Non-uniform attacks against one-way functions and PRGs. Electron. Colloquium Comput. Complex. Anindya De, Luca Trevisan, Madhur Tulsiani
2009	—	`conf`	Pseudorandom Bit Generators That Fool Modular Sums. APPROX-RANDOM Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan
2009	A	`conf`	Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. CCC Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan
2008	J	`jnl`	Approximation Algorithms for Unique Games. Theory Comput. Luca Trevisan
2008	A*	`conf`	Average-case Complexity. FOCS Luca Trevisan
2008	A*	`conf`	Dense Subsets of Pseudorandom Sets. FOCS Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan
2008	J	`jnl`	Dense Subsets of Pseudorandom Sets. Electron. Colloquium Comput. Complex. Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan
2008	—	`ch.`	Learning Heavy Fourier Coefficients of Boolean Functions. Encyclopedia of Algorithms Luca Trevisan
2008	J	`jnl`	Max Cut and the Smallest Eigenvalue CoRR Luca Trevisan
2008	J	`jnl`	Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Electron. Colloquium Comput. Complex. Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan
2007	A	`conf`	A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. CCC Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
2007	A*	`conf`	Amplifying Collision Resistance: A Complexity-Theoretic Treatment. CRYPTO Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee
2007	Misc	`conf`	Fun with Sub-linear Time Algorithms. FUN Luca Trevisan
2007	J	`jnl`	Pseudorandomness and Average-Case Complexity Via Uniform Reductions. Comput. Complex. Luca Trevisan, Salil P. Vadhan
2007	A*	`conf`	Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. STOC Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
2006	J	`jnl`	A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. Electron. Colloquium Comput. Complex. Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
2006	J	`jnl`	Average-Case Complexity CoRR Andrej Bogdanov, Luca Trevisan
2006	J	`jnl`	Average-Case Complexity. Electron. Colloquium Comput. Complex. Andrej Bogdanov, Luca Trevisan
2006	J	`jnl`	Average-Case Complexity. Found. Trends Theor. Comput. Sci. Andrej Bogdanov, Luca Trevisan
2006	A*	`conf`	Gowers uniformity, influence of variables, and PCPs. STOC Alex Samorodnitsky, Luca Trevisan
2006	J	`jnl`	Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complex. Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
2006	J	`jnl`	On Worst-Case to Average-Case Reductions for NP Problems. SIAM J. Comput. Andrej Bogdanov, Luca Trevisan
2006	J	`jnl`	On epsilon-biased generators in NC Random Struct. Algorithms Elchanan Mossel, Amir Shpilka, Luca Trevisan
2006	A*	`conf`	Pseudorandom walks on regular digraphs and the RL vs. L problem. STOC Omer Reingold, Luca Trevisan, Salil P. Vadhan
2006	J	`jnl`	Pseudorandomness and Combinatorial Constructions CoRR Luca Trevisan
2006	J	`jnl`	Pseudorandomness and Combinatorial Constructions Electron. Colloquium Comput. Complex. Luca Trevisan
2006	J	`jnl`	Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. Electron. Colloquium Comput. Complex. Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
2005	J	`jnl`	Approximating Succinct MaxSat. J. Log. Comput. Christian Schallhart, Luca Trevisan
2005	J	`jnl`	Approximating the Minimum Spanning Tree Weight in Sublinear Time. SIAM J. Comput. Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan
2005	J	`jnl`	Approximation Algorithms for Unique Games Electron. Colloquium Comput. Complex. Luca Trevisan
2005	A*	`conf`	Approximation Algorithms for Unique Games. FOCS Luca Trevisan
2005	—	`ed.`	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 Chandra Chekuri, Klaus Jansen, José D. P. Rolim, Luca Trevisan
2005	J	`jnl`	Bounds on the Efficiency of Generic Cryptographic Constructions. SIAM J. Comput. Rosario Gennaro, Yael Gertner, Jonathan Katz, Luca Trevisan
2005	J	`jnl`	Compression of Samplable Sources Electron. Colloquium Comput. Complex. Luca Trevisan, Salil P. Vadhan, David Zuckerman
2005	J	`jnl`	Compression of Samplable Sources. Comput. Complex. Luca Trevisan, Salil P. Vadhan, David Zuckerman
2005	J	`jnl`	Gowers Uniformity, Influence of Variables, and PCPs CoRR Alex Samorodnitsky, Luca Trevisan
2005	J	`jnl`	Gowers Uniformity, Influence of Variables, and PCPs Electron. Colloquium Comput. Complex. Alex Samorodnitsky, Luca Trevisan
2005	A*	`conf`	Hierarchies for semantic classes. STOC Lance Fortnow, Rahul Santhanam, Luca Trevisan
2005	B	`conf`	On Hardness Amplification of One-Way Functions. TCC Henry C. Lin, Luca Trevisan, Hoeteck Wee
2005	J	`jnl`	On Worst-Case to Average-Case Reductions for NP Problems Electron. Colloquium Comput. Complex. Andrej Bogdanov, Luca Trevisan
2005	A*	`conf`	On uniform amplification of hardness in NP. STOC Luca Trevisan
2005	J	`jnl`	Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem Electron. Colloquium Comput. Complex. Omer Reingold, Luca Trevisan, Salil P. Vadhan
2005	—	`conf`	The Complexity of Making Unique Choices: Approximating 1-in- k SAT. APPROX-RANDOM Venkatesan Guruswami, Luca Trevisan
2005	J	`jnl`	The approximability of non-Boolean satisfiability problems and restricted integer programming. Theor. Comput. Sci. Maria J. Serna, Luca Trevisan, Fatos Xhafa
2004	—	`conf`	A Note on Approximate Counting for k-DNF. APPROX-RANDOM Luca Trevisan
2004	A	`conf`	Compression of Samplable Sources. CCC Luca Trevisan, Salil P. Vadhan, David Zuckerman
2004	J	`jnl`	From logarithmic advice to single-bit advice Electron. Colloquium Comput. Complex. Oded Goldreich, Madhu Sudan, Luca Trevisan
2004	J	`jnl`	Inapproximability of Combinatorial Optimization Problems CoRR Luca Trevisan
2004	J	`jnl`	Inapproximability of Combinatorial Optimization Problems Electron. Colloquium Comput. Complex. Luca Trevisan
2004	B	`conf`	List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument. TCC Cynthia Dwork, Ronen Shaltiel, Adam D. Smith, Luca Trevisan
2004	A	`conf`	Lower Bounds for Testing Bipartiteness in Dense Graphs. CCC Andrej Bogdanov, Luca Trevisan
2004	B	`conf`	Notions of Reducibility between Cryptographic Primitives. TCC Omer Reingold, Luca Trevisan, Salil P. Vadhan
2004	J	`jnl`	On Local Versus Global Satisfiability. SIAM J. Discret. Math. Luca Trevisan
2004	J	`jnl`	Promise Hierarchies Electron. Colloquium Comput. Complex. Lance Fortnow, Rahul Santhanam, Luca Trevisan
2004	—	`ch.`	Pseudorandomness - Part II. Computational Complexity Theory Luca Trevisan
2004	J	`jnl`	Some Applications of Coding Theory in Computational Complexity CoRR Luca Trevisan
2004	J	`jnl`	Some Applications of Coding Theory in Computational Complexity Electron. Colloquium Comput. Complex. Luca Trevisan
2003	J	`jnl`	An epsilon-Biased Generator in NC0 Electron. Colloquium Comput. Complex. Luca Trevisan
2003	C	`conf`	Error-Correcting Codes in Complexity Theory. CIAC Luca Trevisan
2003	J	`jnl`	List Decoding Using the XOR Lemma Electron. Colloquium Comput. Complex. Luca Trevisan
2003	A*	`conf`	List-Decoding Using The XOR Lemma. FOCS Luca Trevisan
2003	A*	`conf`	On Worst-Case to Average-Case Reductions for NP Problems. FOCS Andrej Bogdanov, Luca Trevisan
2003	A*	`conf`	On e-Biased Generators in NC0. FOCS Elchanan Mossel, Amir Shpilka, Luca Trevisan
2003	J	`jnl`	On epsilon-Biased Generators in NC0 Electron. Colloquium Comput. Complex. Elchanan Mossel, Amir Shpilka, Luca Trevisan
2003	J	`jnl`	Three theorems regarding testing graph properties. Random Struct. Algorithms Oded Goldreich, Luca Trevisan
2002	A*	`conf`	A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. FOCS Andrej Bogdanov, Kenji Obata, Luca Trevisan
2002	J	`jnl`	A Note on Deterministic Approximate Counting for k-DNF Electron. Colloquium Comput. Complex. Luca Trevisan
2002	—	`conf`	Counting Distinct Elements in a Data Stream. RANDOM Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan
2002	A	`conf`	Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. CCC Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
2002	J	`jnl`	Lower Bounds for Testing Bipartiteness in Dense Graphs Electron. Colloquium Comput. Complex. Andrej Bogdanov, Luca Trevisan
2002	A	`conf`	Pseudorandomness and Average-Case Complexity via Uniform Reductions. CCC Luca Trevisan, Salil P. Vadhan
2002	A	`conf`	Streaming Computation of Combinatorial Objects. CCC Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel
2001	J	`jnl`	Approximating layout problems on random graphs. Discret. Math. Josep Díaz, Jordi Petit, Maria J. Serna, Luca Trevisan
2001	A*	`conf`	Approximating the Minimum Spanning Tree Weight in Sublinear Time. ICALP Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan
2001	—	`ed.`	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 Michel X. Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan
2001	—	`conf`	Error-Correcting Codes and Pseudorandom Projections. RANDOM-APPROX Luca Trevisan
2001	J	`jnl`	Extractors and pseudorandom generators. J. ACM Luca Trevisan
2001	J	`jnl`	Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval Electron. Colloquium Comput. Complex. Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan
2001	A*	`conf`	Non-approximability results for optimization problems on bounded degree instances. STOC Luca Trevisan
2001	J	`jnl`	On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. Inf. Comput. Pierluigi Crescenzi, Riccardo Silvestri, Luca Trevisan
2001	J	`jnl`	Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci. Madhu Sudan, Luca Trevisan, Salil P. Vadhan
2001	A*	`conf`	Three Theorems Regarding Testing Graph Properties. FOCS Oded Goldreich, Luca Trevisan
2001	J	`jnl`	Three Theorems regarding Testing Graph Properties. Electron. Colloquium Comput. Complex. Oded Goldreich, Luca Trevisan
2000	A*	`conf`	A PCP characterization of NP with optimal amortized query complexity. STOC Alex Samorodnitsky, Luca Trevisan
2000	A	`conf`	A Survey of Optimal PCP Characterizations of NP. CCC Luca Trevisan
2000	J	`jnl`	A complexity analysis of bisimilarity for value-passing processes. Theor. Comput. Sci. Michele Boreale, Luca Trevisan
2000	J	`jnl`	Approximating Satisfiable Satisfiability Problems. Algorithmica Luca Trevisan
2000	J	`jnl`	Erratum: A Correction to "Parallel Approximation Algorithms by Positive Linear Programming". Algorithmica Luca Trevisan
2000	A*	`conf`	Extracting Randomness from Samplable Distributions. FOCS Luca Trevisan, Salil P. Vadhan
2000	J	`jnl`	Gadgets, Approximation, and Linear Programming. SIAM J. Comput. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
2000	J	`jnl`	Interactive and probabilistic proof-checking. Ann. Pure Appl. Log. Luca Trevisan
2000	J	`jnl`	Lower Bounds on the Efficiency of Generic Cryptographic Constructions Electron. Colloquium Comput. Complex. Rosario Gennaro, Luca Trevisan
2000	A*	`conf`	Lower Bounds on the Efficiency of Generic Cryptographic Constructions. FOCS Rosario Gennaro, Luca Trevisan
2000	J	`jnl`	Lower Bounds on the Efficiency of Generic Cryptographic Constructions. IACR Cryptol. ePrint Arch. Rosario Gennaro, Luca Trevisan
2000	J	`jnl`	On Approximation Scheme Preserving Reducibility and Its Applications. Theory Comput. Syst. Pierluigi Crescenzi, Luca Trevisan
2000	A*	`conf`	On the efficiency of local decoding procedures for error-correcting codes. STOC Jonathan Katz, Luca Trevisan
2000	J	`jnl`	The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson
2000	J	`jnl`	When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree. SIAM J. Comput. Luca Trevisan
1999	A*	`conf`	Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). STOC Luca Trevisan
1999	J	`jnl`	Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints. Theor. Comput. Sci. Andrea E. F. Clementi, Luca Trevisan
1999	J	`jnl`	Max NP-completeness Made Easy. Theor. Comput. Sci. Pierluigi Crescenzi, Luca Trevisan
1999	A*	`conf`	Pseudorandom Generators Without the XOR Lemma (Extended Abstract). STOC Madhu Sudan, Luca Trevisan, Salil P. Vadhan
1999	A	`conf`	Pseudorandom Generators without the XOR Lemma (Abstract). CCC Madhu Sudan, Luca Trevisan, Salil P. Vadhan
1999	J	`jnl`	Structure in Approximation Classes. SIAM J. Comput. Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan
1999	J	`jnl`	Weak Random Sources, Hitting Sets, and BPP Simulations. SIAM J. Comput. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan
1998	J	`jnl`	A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms. J. Comb. Optim. José D. P. Rolim, Luca Trevisan
1998	A*	`conf`	A Tight Characterization of NP with 3 Query PCPs. FOCS Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
1998	J	`jnl`	A tight characterization of NP with 3 query PCPs Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
1998	J	`jnl`	Constructions of Near-Optimal Extractors Using Pseudo-Random Generators Electron. Colloquium Comput. Complex. Luca Trevisan
1998	J	`jnl`	Parallel Approximation Algorithms by Positive Linear Programming. Algorithmica Luca Trevisan
1998	A*	`conf`	Probabilistically Checkable Proofs with Low Amortized Query Complexity. FOCS Madhu Sudan, Luca Trevisan
1998	J	`jnl`	Probabilistically checkable proofs with low amortized query complexity Electron. Colloquium Comput. Complex. Madhu Sudan, Luca Trevisan
1998	J	`jnl`	Pseudorandom generators without the XOR Lemma Electron. Colloquium Comput. Complex. Madhu Sudan, Luca Trevisan, Salil P. Vadhan
1998	J	`jnl`	Recent Advances Towards Proving P = BPP. Bull. EATCS Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan
1998	J	`jnl`	Recycling Queries in PCPs and in Linearity Tests Electron. Colloquium Comput. Complex. Luca Trevisan
1998	A*	`conf`	Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). STOC Luca Trevisan
1998	A	`conf`	The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. STACS Maria J. Serna, Luca Trevisan, Fatos Xhafa
1998	J	`jnl`	The Parallel Complexity of Positive Linear Programming. Parallel Process. Lett. Luca Trevisan, Fatos Xhafa
1997	—	`conf`	A case study of de-randomization methods for combinatorial approximation algorithms. Network Design: Connectivity and Facilities Location José D. P. Rolim, Luca Trevisan
1997	A	`conf`	Approximating Satisfiable Satisfiability Problems (Extended Abstract). ESA Luca Trevisan
1997	A	`conf`	Constraint Satisfaction: The Approximability of Minimization Problems. CCC Sanjeev Khanna, Madhu Sudan, Luca Trevisan
1997	J	`jnl`	MAX NP-Completeness Made Easy Electron. Colloquium Comput. Complex. Pierluigi Crescenzi, Luca Trevisan
1997	J	`jnl`	On Local versus Global Satisfiability Electron. Colloquium Comput. Complex. Luca Trevisan
1997	J	`jnl`	On the Efficiency of Polynomial Time Approximation Schemes Electron. Colloquium Comput. Complex. Marco Cesati, Luca Trevisan
1997	J	`jnl`	On the Efficiency of Polynomial Time Approximation Schemes. Inf. Process. Lett. Marco Cesati, Luca Trevisan
1997	J	`jnl`	Weak Random Sources, Hitting Sets, and BPP Simulations Electron. Colloquium Comput. Complex. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan
1997	A*	`conf`	Weak Random Sources, Hitting Sets, and BPP Simulations. FOCS Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan
1997	A*	`conf`	When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). STOC Luca Trevisan
1996	J	`jnl`	A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees. Inf. Process. Lett. Luca Trevisan
1996	B	`conf`	Bisimilarity Problems Requiring Exponential Time. MFCS Michele Boreale, Luca Trevisan
1996	J	`jnl`	Constraint satisfaction: The approximability of minimization problems. Electron. Colloquium Comput. Complex. Sanjeev Khanna, Madhu Sudan, Luca Trevisan
1996	A*	`conf`	Gadgets, Approximation, and Linear Programming (extended abstract). FOCS Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
1996	J	`jnl`	Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints Electron. Colloquium Comput. Complex. Andrea E. F. Clementi, Luca Trevisan
1996	Misc	`conf`	Improved Non-approximability Results for Vertex Cover with Density Constraints. COCOON Andrea E. F. Clementi, Luca Trevisan
1996	J	`jnl`	On the Approximability of the Multi-dimensional Euclidean TSP Electron. Colloquium Comput. Complex. Luca Trevisan
1996	J	`jnl`	On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem. RAIRO Theor. Informatics Appl. Pierluigi Crescenzi, Luca Trevisan
1996	A	`conf`	Positive Linear Programming, Parallel Approximation and PCP's. ESA Luca Trevisan
1996	J	`jnl`	Structure in Approximation Classes Electron. Colloquium Comput. Complex. Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan
1996	—	`conf`	To Weight or Not to Weight: Where is the Question? ISTCS Pierluigi Crescenzi, Riccardo Silvestri, Luca Trevisan
1995	—	`conf`	On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract). FSTTCS Michele Boreale, Luca Trevisan
1995	Misc	`conf`	Structure in Approximation Classes (Extended Abstract). COCOON Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan
1994	B	`conf`	Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract). WG Pierluigi Crescenzi, Luca Trevisan
1994	—	`conf`	On Approximation Scheme Preserving Reducability and Its Applications. FSTTCS Pierluigi Crescenzi, Luca Trevisan