Luca Trevisan

ORCID

Publication Activity (10 Years)

Years Active: 1994-2024
Publications (10 Years): 61

Top Venues

Publications

Gabriele Manduchi, Andrea Rigoni, Luca Trevisan, Tommaso Patton
A Versatile Board for Event-Driven Data Acquisition. Sensors 24 (5) (2024)
Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan
New SDP Roundings and Certifiable Approximation for Cubic Optimization. SODA (2024)
Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
Bond percolation in small-world graphs with power-law distribution. Theor. Comput. Sci. 1011 (2024)
Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, Isabella Ziccardi
The Minority Dynamics and the Power of Synchronicity. SODA (2024)
Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, Isabella Ziccardi
The Minority Dynamics and the Power of Synchronicity. CoRR (2023)
Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
Expansion and flooding in dynamic random networks with node churn. Random Struct. Algorithms 63 (1) (2023)
Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
Bond Percolation in Small-World Graphs with Power-Law Distribution. SAND (2023)
Tommaso d'Orsi, Luca Trevisan
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. CCC (2023)
Luca Becchetti, Andrea E. F. Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, Robin Vacus
On the Role of Memory in Robust Opinion Dynamics. IJCAI (2023)
Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan
New SDP Roundings and Certifiable Approximation for Cubic Optimization. CoRR (2023)
Luca Becchetti, Andrea E. F. Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, Robin Vacus
On the Role of Memory in Robust Opinion Dynamics. CoRR (2023)
Luca Becchetti, Arthur Carvalho Walraven da Cuhna, Andrea E. F. Clementi, Francesco D'Amore, Hicham Lesfari, Emanuele Natale, Luca Trevisan
On the Multidimensional Random Subset Sum Problem. CoRR (2022)
Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
Bond Percolation in Small-World Graphs with Power-Law Distribution. CoRR (2022)
Antares Chen, Jonathan Shi, Luca Trevisan
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification. SODA (2022)
Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
. Theory Comput. 18 (2022)
Luca Becchetti, Andrea E. F. Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
Percolation and Epidemic Processes in One-Dimensional Small-World Networks - (Extended Abstract). LATIN (2022)
Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, Luca Trevisan
Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models. AISTATS (2022)
Tommaso Fedullo, Alberto Morato, Giovanni Peserico, Luca Trevisan, Federico Tramarin, Stefano Vitturi, Luigi Rovati
An IoT Measurement System Based on LoRaWAN for Additive Manufacturing. Sensors 22 (15) (2022)
Tommaso d'Orsi, Luca Trevisan
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. CoRR (2022)
Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, Luca Trevisan
Correlation Clustering Reconstruction in Semi-Adversarial Models. CoRR (2021)
Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
Expansion and Flooding in Dynamic Random Networks with Node Churn. ICDCS (2021)
Luca Trevisan
Introducing The Theory Blogs Column. Bull. EATCS 135 (2021)
Luca Becchetti, Andrea E. F. Clementi, Riccardo Denni, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks. CoRR (2021)
Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan
Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming. SIAM J. Discret. Math. 35 (3) (2021)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. SIAM J. Comput. 49 (4) (2020)
Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan
Lower Bounds for Max-Cut via Semidefinite Programming. LATIN (2020)
Antares Chen, Jonathan Shi, Luca Trevisan
Cut Sparsification of the Clique Beyond the Ramanujan Bound. CoRR (2020)
Theo McKenzie, Hermish Mehta, Luca Trevisan
A New Algorithm for the Robust Semi-random Independent Set Problem. SODA (2020)
Luca Trevisan, Stefano Vitturi, Federico Tramarin, Alberto Morato
An IIoT System to Monitor 3D-Printed Artifacts via LoRaWAN Embedded Sensors. ETFA (2020)
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
Subexponential LPs Approximate Max-Cut. FOCS (2020)
Andrea E. F. Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, Luca Trevisan
Consensus vs Broadcast, with and Without Noise (Extended Abstract). ITCS (2020)
Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi
Expansion and Flooding in Dynamic Random Networks with Node Churn. CoRR (2020)
Stefano Vitturi, Luca Trevisan, Alberto Morato, Guglielmo Frigo, Federico Tramarin
Evaluation of LoRaWAN for Sensor Data Collection in an IIoT-based Additive Manufacturing Project. I2MTC (2020)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
Find Your Place: Simple Distributed Algorithms for Community Detection. SIAM J. Comput. 49 (4) (2020)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
Finding a Bounded-Degree Expander Inside a Dense One. SODA (2020)
Nikhil Bansal, Ola Svensson, Luca Trevisan
New Notions and Constructions of Sparsification for Graphs and Hypergraphs. CoRR (2019)
Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan
Optimal Lower Bounds for Sketching Graph Cuts. SODA (2019)
Jess Banks, Luca Trevisan
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs. CoRR (2019)
Nikhil Bansal, Ola Svensson, Luca Trevisan
New Notions and Constructions of Sparsification for Graphs and Hypergraphs. FOCS (2019)
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
Subexponential LPs Approximate Max-Cut. CoRR (2019)
Luca Becchetti, Andrea E. F. Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
Average Whenever You Meet: Opportunistic Protocols for Community Detection. ESA (2018)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
Finding a Bounded-Degree Expander Inside a Dense One. CoRR (2018)
Theo McKenzie, Hermish Mehta, Luca Trevisan
A New Algorithm for the Robust Semi-random Independent Set Problem. CoRR (2018)
Charles Carlson, Alexandra Kolla, Luca Trevisan
A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs. CoRR (2018)
Andrea E. F. Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, Luca Trevisan
Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise. CoRR (2018)
Pasin Manurangsi, Luca Trevisan
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems. CoRR (2018)
Nikhil Srivastava, Luca Trevisan
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification. SODA (2018)
Pasin Manurangsi, Luca Trevisan
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut. APPROX-RANDOM (2018)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. FOCS (2017)
Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. SODA (2017)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
Find Your Place: Simple Distributed Algorithms for Community Detection. SODA (2017)
Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan
Optimal Lower Bounds for Sketching Graph Cuts. CoRR (2017)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan
Friend or Foe? Population Protocols can perform Community Detection. CoRR (2017)
Nikhil Srivastava, Luca Trevisan
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification. CoRR (2017)
Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. CoRR (2017)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan
Simple dynamics for plurality consensus. Distributed Comput. 30 (4) (2017)
Guy Kindler, Alexandra Kolla, Luca Trevisan
Approximation of non-boolean 2CSP. SODA (2016)
Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
Near-Optimal UGC-hardness of Approximating Max k-CSP_R. APPROX-RANDOM (2016)
Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan
Almost Optimal Local Graph Clustering Using Evolving Sets. J. ACM 63 (2) (2016)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
Stabilizing Consensus with Many Opinions. SODA (2016)
Michele Borassi, Pierluigi Crescenzi, Luca Trevisan
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. CoRR (2016)
Guy Kindler, Alexandra Kolla, Luca Trevisan
Approximation of non-boolean 2CSP. CoRR (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR (2015)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
Find Your Place: Simple Distributed Algorithms for Community Detection. CoRR (2015)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan
Stabilizing Consensus with Many Opinions. CoRR (2015)
Shayan Oveis Gharan, Luca Trevisan
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. Theory Comput. 11 (2015)
Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
Near-Optimal UGC-hardness of Approximating Max k-CSP_R. CoRR (2015)
Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan
Unique Games on the Hypercube. Chic. J. Theor. Comput. Sci. 2015 (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. 22 (2015)
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. 15 (11&12) (2015)
Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan
Information spreading in dynamic graphs. Distributed Comput. 28 (1) (2015)
James R. Lee, Shayan Oveis Gharan, Luca Trevisan
Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities. J. ACM 61 (6) (2014)
James Cook, Omid Etesami, Rachel Miller, Luca Trevisan
On the One-Way Function Candidate Proposed by Goldreich. ACM Trans. Comput. Theory 6 (3) (2014)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan
Simple dynamics for plurality consensus. SPAA (2014)
Lap Chi Lau, Tal Malkin, Ryan O'Donnell, Luca Trevisan
Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). SIAM J. Comput. 43 (1) (2014)
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Quantum lower bound for inverting a permutation with advice. Electron. Colloquium Comput. Complex. 21 (2014)
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Quantum lower bound for inverting a permutation with advice. CoRR (2014)
Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan
Unique Games on the Hypercube. CoRR (2014)
Shayan Oveis Gharan, Luca Trevisan
Partitioning into Expanders. SODA (2014)
Shayan Oveis Gharan, Luca Trevisan
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROX-RANDOM (2013)
Shayan Oveis Gharan, Luca Trevisan
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank CoRR (2013)
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan
Simple Dynamics for Majority Consensus. CoRR (2013)
Luca Trevisan, Tongke Xue
A Derandomized Switching Lemma and an Improved Derandomization of AC0. Computational Complexity Conference (2013)
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. STOC (2013)
Shayan Oveis Gharan, Luca Trevisan
Partitioning into Expanders. CoRR (2013)
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap CoRR (2013)
Luca Trevisan
Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut? CoRR (2013)
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan
Better Pseudorandom Generators from Milder Pseudorandom Restrictions CoRR (2012)
Shayan Oveis Gharan, Luca Trevisan
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs CoRR (2012)
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan
Better pseudorandom generators from milder pseudorandom restrictions. Electron. Colloquium Comput. Complex. 19 (2012)
James R. Lee, Shayan Oveis Gharan, Luca Trevisan
Multi-way spectral partitioning and higher-order cheeger inequalities. STOC (2012)
Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan
Information spreading in dynamic graphs. PODC (2012)
James Cook, Omid Etesami, Rachel Miller, Luca Trevisan
On the One-Way Function Candidate Proposed by Goldreich. Electron. Colloquium Comput. Complex. 19 (2012)
Shayan Oveis Gharan, Luca Trevisan
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. FOCS (2012)
Shayan Oveis Gharan, Luca Trevisan
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues CoRR (2012)
Luca Trevisan
Pseudorandomness and derandomization. XRDS 18 (3) (2012)
Luca Trevisan
A Derandomized Switching Lemma and an Improved Derandomization of AC0. Electron. Colloquium Comput. Complex. 19 (2012)
Shayan Oveis Gharan, Luca Trevisan
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering CoRR (2012)
Luca Trevisan
Max Cut and the Smallest Eigenvalue. SIAM J. Comput. 41 (6) (2012)

Luca Trevisan.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Luca Trevisan