On Approximation Scheme Preserving Reducability and Its Applications. - Pierluigi Crescenzi; Luca Trevisan 001 (FSTTCS, 1994)

Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract). - Pierluigi Crescenzi; Luca Trevisan 001 (WG, 1994)

Structure in Approximation Classes (Extended Abstract). - Pierluigi Crescenzi; Viggo Kann; Riccardo Silvestri; Luca Trevisan 001 (COCOON, 1995)

On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract). - Michele Boreale; Luca Trevisan 001 (FSTTCS, 1995)

Improved Non-approximability Results for Vertex Cover with Density Constraints. - Andrea E. F. Clementi; Luca Trevisan 001 (COCOON, 1996)

Positive Linear Programming, Parallel Approximation and PCP's. - Luca Trevisan 001 (ESA, 1996)

Gadgets, Approximation, and Linear Programming (extended abstract). - Luca Trevisan 001; Gregory B. Sorkin; Madhu Sudan 001; David P. Williamson (FOCS, 1996)

To Weight or Not to Weight: Where is the Question? - Pierluigi Crescenzi; Riccardo Silvestri; Luca Trevisan 001 (ISTCS, 1996)

Bisimilarity Problems Requiring Exponential Time. - Michele Boreale; Luca Trevisan 001 (MFCS, 1996)

On the Approximability of the Multi-dimensional Euclidean TSP - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 1996)

Constraint satisfaction: The approximability of minimization problems. - Sanjeev Khanna; Madhu Sudan 001; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 1996)

A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees. - Luca Trevisan 001 (Inf. Process. Lett., 1996)

On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem. - Pierluigi Crescenzi; Luca Trevisan 001 (RAIRO Theor. Informatics Appl., 1996)

Approximating Satisfiable Satisfiability Problems (Extended Abstract). - Luca Trevisan 001 (ESA, 1997)

When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). - Luca Trevisan 001 (STOC, 1997)

On Local versus Global Satisfiability - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 1997)

On the Efficiency of Polynomial Time Approximation Schemes. - Marco Cesati; Luca Trevisan 001 (Inf. Process. Lett., 1997)

The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. - Maria J. Serna; Luca Trevisan 001; Fatos Xhafa (STACS, 1998)

Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). - Luca Trevisan 001 (STOC, 1998)

Parallel Approximation Algorithms by Positive Linear Programming. - Luca Trevisan 001 (Algorithmica, 1998)

Recent Advances Towards Proving P = BPP. - Andrea E. F. Clementi; José D. P. Rolim; Luca Trevisan 001 (Bull. EATCS, 1998)

Recycling Queries in PCPs and in Linearity Tests - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 1998)

A tight characterization of NP with 3 query PCPs - Venkatesan Guruswami; Daniel Lewin 001; Madhu Sudan 001; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 1998)

Probabilistically checkable proofs with low amortized query complexity - Madhu Sudan 001; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 1998)

Constructions of Near-Optimal Extractors Using Pseudo-Random Generators - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 1998)

A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms. - José D. P. Rolim; Luca Trevisan 001 (J. Comb. Optim., 1998)

The Parallel Complexity of Positive Linear Programming. - Luca Trevisan 001; Fatos Xhafa (Parallel Process. Lett., 1998)

Pseudorandom Generators without the XOR Lemma (Abstract). - Madhu Sudan 001; Luca Trevisan 001; Salil P. Vadhan (CCC, 1999)

Pseudorandom Generators Without the XOR Lemma (Extended Abstract). - Madhu Sudan 001; Luca Trevisan 001; Salil P. Vadhan (STOC, 1999)

Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). - Luca Trevisan 001 (STOC, 1999)

Weak Random Sources, Hitting Sets, and BPP Simulations. - Alexander E. Andreev; Andrea E. F. Clementi; José D. P. Rolim; Luca Trevisan 001 (SIAM J. Comput., 1999)

Structure in Approximation Classes. - Pierluigi Crescenzi; Viggo Kann; Riccardo Silvestri; Luca Trevisan 001 (SIAM J. Comput., 1999)

Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints. - Andrea E. F. Clementi; Luca Trevisan 001 (Theor. Comput. Sci., 1999)

Max NP-completeness Made Easy. - Pierluigi Crescenzi; Luca Trevisan 001 (Theor. Comput. Sci., 1999)

A Survey of Optimal PCP Characterizations of NP. - Luca Trevisan 001 (CCC, 2000)

Extracting Randomness from Samplable Distributions. - Luca Trevisan 001; Salil P. Vadhan (FOCS, 2000)

On the efficiency of local decoding procedures for error-correcting codes. - Jonathan Katz; Luca Trevisan 001 (STOC, 2000)

A PCP characterization of NP with optimal amortized query complexity. - Alex Samorodnitsky; Luca Trevisan 001 (STOC, 2000)

Erratum: A Correction to "Parallel Approximation Algorithms by Positive Linear Programming". - Luca Trevisan 001 (Algorithmica, 2000)

Approximating Satisfiable Satisfiability Problems. - Luca Trevisan 001 (Algorithmica, 2000)

Interactive and probabilistic proof-checking. - Luca Trevisan 001 (Ann. Pure Appl. Log., 2000)

Lower Bounds on the Efficiency of Generic Cryptographic Constructions - Rosario Gennaro; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2000)

On Approximation Scheme Preserving Reducibility and Its Applications. - Pierluigi Crescenzi; Luca Trevisan 001 (Theory Comput. Syst., 2000)

The Approximability of Constraint Satisfaction Problems. - Sanjeev Khanna; Madhu Sudan 001; Luca Trevisan 001; David P. Williamson (SIAM J. Comput., 2000)

When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree. - Luca Trevisan 001 (SIAM J. Comput., 2000)

Gadgets, Approximation, and Linear Programming. - Luca Trevisan 001; Gregory B. Sorkin; Madhu Sudan 001; David P. Williamson (SIAM J. Comput., 2000)

A complexity analysis of bisimilarity for value-passing processes. - Michele Boreale; Luca Trevisan 001 (Theor. Comput. Sci., 2000)

Error-Correcting Codes and Pseudorandom Projections. - Luca Trevisan 001 (RANDOM-APPROX, 2001)

Non-approximability results for optimization problems on bounded degree instances. - Luca Trevisan 001 (STOC, 2001)

Approximating layout problems on random graphs. - Josep Díaz; Jordi Petit; Maria J. Serna; Luca Trevisan 001 (Discret. Math., 2001)

Three Theorems regarding Testing Graph Properties. - Oded Goldreich 001; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2001)

On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. - Pierluigi Crescenzi; Riccardo Silvestri; Luca Trevisan 001 (Inf. Comput., 2001)

Extractors and pseudorandom generators. - Luca Trevisan 001 (J. ACM, 2001)

Pseudorandom Generators without the XOR Lemma. - Madhu Sudan 001; Luca Trevisan 001; Salil P. Vadhan (J. Comput. Syst. Sci., 2001)

Streaming Computation of Combinatorial Objects. - Ziv Bar-Yossef; Luca Trevisan 001; Omer Reingold; Ronen Shaltiel (CCC, 2002)

A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. - Andrej Bogdanov; Kenji Obata; Luca Trevisan 001 (FOCS, 2002)

Counting Distinct Elements in a Data Stream. - Ziv Bar-Yossef; T. S. Jayram; Ravi Kumar 001; D. Sivakumar 001; Luca Trevisan 001 (RANDOM, 2002)

Lower Bounds for Testing Bipartiteness in Dense Graphs - Andrej Bogdanov; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2002)

A Note on Deterministic Approximate Counting for k-DNF - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2002)

Error-Correcting Codes in Complexity Theory. - Luca Trevisan 001 (CIAC, 2003)

On e-Biased Generators in NC0. - Elchanan Mossel; Amir Shpilka; Luca Trevisan 001 (FOCS, 2003)

An epsilon-Biased Generator in NC0 - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2003)

List Decoding Using the XOR Lemma - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2003)

On epsilon-Biased Generators in NC0 - Elchanan Mossel; Amir Shpilka; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2003)

Pseudorandomness - Part II. - Luca Trevisan 001 (Computational Complexity Theory, 2004)

A Note on Approximate Counting for k-DNF. - Luca Trevisan 001 (APPROX-RANDOM, 2004)

List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument. - Cynthia Dwork; Ronen Shaltiel; Adam D. Smith 001; Luca Trevisan 001 (TCC, 2004)

Notions of Reducibility between Cryptographic Primitives. - Omer Reingold; Luca Trevisan 001; Salil P. Vadhan (TCC, 2004)

Some Applications of Coding Theory in Computational Complexity - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2004)

Inapproximability of Combinatorial Optimization Problems - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2004)

From logarithmic advice to single-bit advice - Oded Goldreich 001; Madhu Sudan 001; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2004)

Promise Hierarchies - Lance Fortnow; Rahul Santhanam; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2004)

The Complexity of Making Unique Choices: Approximating 1-in- k SAT. - Venkatesan Guruswami; Luca Trevisan 001 (APPROX-RANDOM, 2005)

Hierarchies for semantic classes. - Lance Fortnow; Rahul Santhanam; Luca Trevisan 001 (STOC, 2005)

On uniform amplification of hardness in NP. - Luca Trevisan 001 (STOC, 2005)

On Hardness Amplification of One-Way Functions. - Henry C. Lin; Luca Trevisan 001; Hoeteck Wee (TCC, 2005)

Compression of Samplable Sources. - Luca Trevisan 001; Salil P. Vadhan; David Zuckerman (Comput. Complex., 2005)

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem - Omer Reingold; Luca Trevisan 001; Salil P. Vadhan (Electron. Colloquium Comput. Complex., 2005)

Approximation Algorithms for Unique Games - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2005)

Approximating Succinct MaxSat. - Christian Schallhart; Luca Trevisan 001 (J. Log. Comput., 2005)

Approximating the Minimum Spanning Tree Weight in Sublinear Time. - Bernard Chazelle; Ronitt Rubinfeld; Luca Trevisan 001 (SIAM J. Comput., 2005)

Bounds on the Efficiency of Generic Cryptographic Constructions. - Rosario Gennaro; Yael Gertner; Jonathan Katz; Luca Trevisan 001 (SIAM J. Comput., 2005)

The approximability of non-Boolean satisfiability problems and restricted integer programming. - Maria J. Serna; Luca Trevisan 001; Fatos Xhafa (Theor. Comput. Sci., 2005)

Pseudorandom walks on regular digraphs and the RL vs. L problem. - Omer Reingold; Luca Trevisan 001; Salil P. Vadhan (STOC, 2006)

Lower bounds for linear locally decodable codes and private information retrieval. - Oded Goldreich 001; Howard J. Karloff; Leonard J. Schulman; Luca Trevisan 001 (Comput. Complex., 2006)

Average-Case Complexity. - Andrej Bogdanov; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2006)

Pseudorandomness and Combinatorial Constructions - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2006)

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. - Grant Schoenebeck; Luca Trevisan 001; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2006)

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. - Grant Schoenebeck; Luca Trevisan 001; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2006)

On epsilon-biased generators in NC0. - Elchanan Mossel; Amir Shpilka; Luca Trevisan 001 (Random Struct. Algorithms, 2006)

On Worst-Case to Average-Case Reductions for NP Problems. - Andrej Bogdanov; Luca Trevisan 001 (SIAM J. Comput., 2006)

Amplifying Collision Resistance: A Complexity-Theoretic Treatment. - Ran Canetti; Ronald L. Rivest; Madhu Sudan 001; Luca Trevisan 001; Salil P. Vadhan; Hoeteck Wee (CRYPTO, 2007)

Fun with Sub-linear Time Algorithms. - Luca Trevisan 001 (FUN, 2007)

Pseudorandomness and Average-Case Complexity Via Uniform Reductions. - Luca Trevisan 001; Salil P. Vadhan (Comput. Complex., 2007)

Average-case Complexity. - Luca Trevisan 001 (FOCS, 2008)

Dense Subsets of Pseudorandom Sets. - Omer Reingold; Luca Trevisan 001; Madhur Tulsiani; Salil P. Vadhan (Electron. Colloquium Comput. Complex., 2008)

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. - Luca Trevisan 001; Madhur Tulsiani; Salil P. Vadhan (Electron. Colloquium Comput. Complex., 2008)

Learning Heavy Fourier Coefficients of Boolean Functions. - Luca Trevisan 001 (Encyclopedia of Algorithms, 2008)

Extractors Using Hardness Amplification. - Anindya De; Luca Trevisan 001 (APPROX-RANDOM, 2009)

Pseudorandom Bit Generators That Fool Modular Sums. - Shachar Lovett; Omer Reingold; Luca Trevisan 001; Salil P. Vadhan (APPROX-RANDOM, 2009)

Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms. - James Cook; Omid Etesami; Rachel Miller; Luca Trevisan 001 (TCC, 2009)

Foreword. - Chandra Chekuri; Luca Trevisan 001 (Algorithmica, 2009)

Improved Pseudorandom Generators for Depth 2 Circuits. - Anindya De; Omid Etesami; Luca Trevisan 001; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2009)

Non-uniform attacks against one-way functions and PRGs. - Anindya De; Luca Trevisan 001; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2009)

Gowers Uniformity, Influence of Variables, and PCPs. - Alex Samorodnitsky; Luca Trevisan 001 (SIAM J. Comput., 2009)

Guest column: additive combinatorics and theoretical computer science. - Luca Trevisan 001 (SIGACT News, 2009)

Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. - Anindya De; Luca Trevisan 001; Madhur Tulsiani (CRYPTO, 2010)

The Program-Enumeration Bottleneck in Average-Case Complexity Theory. - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2010)

From Logarithmic Advice to Single-Bit Advice. - Oded Goldreich 001; Madhu Sudan 001; Luca Trevisan 001 (Studies in Complexity and Cryptography, 2011)

Dense Model Theorems and Their Applications. - Luca Trevisan 001 (TCC, 2011)

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. - Shayan Oveis Gharan; Luca Trevisan 001 (FOCS, 2012)

Multi-way spectral partitioning and higher-order cheeger inequalities. - James R. Lee; Shayan Oveis Gharan; Luca Trevisan 001 (STOC, 2012)

A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues - Shayan Oveis Gharan; Luca Trevisan 001 (CoRR, 2012)

Pseudorandomness and derandomization. - Luca Trevisan 001 (XRDS, 2012)

On the One-Way Function Candidate Proposed by Goldreich. - James Cook; Omid Etesami; Rachel Miller; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2012)

Better pseudorandom generators from milder pseudorandom restrictions. - Parikshit Gopalan; Raghu Meka; Omer Reingold; Luca Trevisan 001; Salil P. Vadhan (Electron. Colloquium Comput. Complex., 2012)

A Derandomized Switching Lemma and an Improved Derandomization of AC0. - Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2012)

Max Cut and the Smallest Eigenvalue. - Luca Trevisan 001 (SIAM J. Comput., 2012)

A Derandomized Switching Lemma and an Improved Derandomization of AC0. - Luca Trevisan 001; Tongke Xue (CCC, 2013)

Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap. - Tsz Chiu Kwok; Lap Chi Lau; Yin Tat Lee; Shayan Oveis Gharan; Luca Trevisan 001 (STOC, 2013)

Simple Dynamics for Majority Consensus. - Luca Becchetti; Andrea Clementi; Emanuele Natale; Francesco Pasquale; Riccardo Silvestri; Luca Trevisan 001 (CoRR, 2013)

Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut? - Luca Trevisan 001 (CoRR, 2013)

Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank - Shayan Oveis Gharan; Luca Trevisan 001 (CoRR, 2013)

Partitioning into Expanders. - Shayan Oveis Gharan; Luca Trevisan 001 (SODA, 2014)

Quantum lower bound for inverting a permutation with advice. - Aran Nayebi; Scott Aaronson; Aleksandrs Belovs; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2014)

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities. - James R. Lee; Shayan Oveis Gharan; Luca Trevisan 001 (J. ACM, 2014)

Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). - Lap Chi Lau; Tal Malkin; Ryan O'Donnell; Luca Trevisan 001 (SIAM J. Comput., 2014)

Unique Games on the Hypercube. - Naman Agarwal; Guy Kindler; Alexandra Kolla; Luca Trevisan 001 (Chic. J. Theor. Comput. Sci., 2015)

Information spreading in dynamic graphs. - Andrea Clementi; Riccardo Silvestri; Luca Trevisan 001 (Distributed Comput., 2015)

Beating the random assignment on constraint satisfaction problems of bounded degree. - Boaz Barak; Ankur Moitra; Ryan O'Donnell; Prasad Raghavendra; Oded Regev 001; David Steurer; Luca Trevisan 001; Aravindan Vijayaraghavan; David Witmer; John Wright 004 (Electron. Colloquium Comput. Complex., 2015)

A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. - Shayan Oveis Gharan; Luca Trevisan 001 (Theory Comput., 2015)

Near-Optimal UGC-hardness of Approximating Max k-CSP_R. - Pasin Manurangsi; Preetum Nakkiran; Luca Trevisan 001 (APPROX-RANDOM, 2016)

Stabilizing Consensus with Many Opinions. - Luca Becchetti; Andrea Clementi; Emanuele Natale; Francesco Pasquale; Luca Trevisan 001 (SODA, 2016)

Approximation of non-boolean 2CSP. - Guy Kindler; Alexandra Kolla; Luca Trevisan 001 (SODA, 2016)

Almost Optimal Local Graph Clustering Using Evolving Sets. - Reid Andersen; Shayan Oveis Gharan; Yuval Peres; Luca Trevisan 001 (J. ACM, 2016)

Learning Heavy Fourier Coefficients of Boolean Functions. - Luca Trevisan 001 (Encyclopedia of Algorithms, 2016)

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. - Parinya Chalermsook; Marek Cygan; Guy Kortsarz; Bundit Laekhanukit; Pasin Manurangsi; Danupon Nanongkai; Luca Trevisan 001 (FOCS, 2017)

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. - Michele Borassi; Pierluigi Crescenzi; Luca Trevisan 001 (SODA, 2017)

Friend or Foe? Population Protocols can perform Community Detection. - Luca Becchetti; Andrea Clementi; Emanuele Natale; Francesco Pasquale; Prasad Raghavendra; Luca Trevisan 001 (CoRR, 2017)

Simple dynamics for plurality consensus. - Luca Becchetti; Andrea Clementi; Emanuele Natale; Francesco Pasquale; Riccardo Silvestri; Luca Trevisan 001 (Distributed Comput., 2017)

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut. - Pasin Manurangsi; Luca Trevisan 001 (APPROX-RANDOM, 2018)

Average Whenever You Meet: Opportunistic Protocols for Community Detection. - Luca Becchetti; Andrea Clementi; Pasin Manurangsi; Emanuele Natale; Francesco Pasquale; Prasad Raghavendra; Luca Trevisan 001 (ESA, 2018)

An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification. - Nikhil Srivastava; Luca Trevisan 001 (SODA, 2018)

Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise. - Andrea Clementi; Luciano Gualà; Emanuele Natale; Francesco Pasquale; Giacomo Scornavacca; Luca Trevisan 001 (CoRR, 2018)

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems. - Pasin Manurangsi; Luca Trevisan 001 (CoRR, 2018)

A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs. - Charles Carlson 002; Alexandra Kolla; Luca Trevisan 001 (CoRR, 2018)

New Notions and Constructions of Sparsification for Graphs and Hypergraphs. - Nikhil Bansal 001; Ola Svensson; Luca Trevisan 001 (FOCS, 2019)

Optimal Lower Bounds for Sketching Graph Cuts. - Charles Carlson 002; Alexandra Kolla; Nikhil Srivastava; Luca Trevisan 001 (SODA, 2019)

Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs. - Jess Banks; Luca Trevisan 001 (CoRR, 2019)

Subexponential LPs Approximate Max-Cut. - Samuel B. Hopkins 001; Tselil Schramm; Luca Trevisan 001 (FOCS, 2020)

Consensus vs Broadcast, with and Without Noise (Extended Abstract). - Andrea Clementi; Luciano Gualà; Emanuele Natale; Francesco Pasquale; Giacomo Scornavacca; Luca Trevisan 001 (ITCS, 2020)

Lower Bounds for Max-Cut via Semidefinite Programming. - Charles Carlson 002; Alexandra Kolla; Ray Li; Nitya Mani; Benny Sudakov; Luca Trevisan 001 (LATIN, 2020)

Finding a Bounded-Degree Expander Inside a Dense One. - Luca Becchetti; Andrea Clementi; Emanuele Natale; Francesco Pasquale; Luca Trevisan 001 (SODA, 2020)

A New Algorithm for the Robust Semi-random Independent Set Problem. - Theo McKenzie; Hermish Mehta; Luca Trevisan 001 (SODA, 2020)

Cut Sparsification of the Clique Beyond the Ramanujan Bound. - Antares Chen; Jonathan Shi; Luca Trevisan 001 (CoRR, 2020)

Find Your Place: Simple Distributed Algorithms for Community Detection. - Luca Becchetti; Andrea E. F. Clementi; Emanuele Natale; Francesco Pasquale; Luca Trevisan 001 (SIAM J. Comput., 2020)

From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More. - Parinya Chalermsook; Marek Cygan; Guy Kortsarz; Bundit Laekhanukit; Pasin Manurangsi; Danupon Nanongkai; Luca Trevisan 001 (SIAM J. Comput., 2020)

Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks. - Luca Becchetti; Andrea Clementi; Riccardo Denni; Francesco Pasquale; Luca Trevisan 001; Isabella Ziccardi (CoRR, 2021)

Correlation Clustering Reconstruction in Semi-Adversarial Models. - Flavio Chierichetti; Alessandro Panconesi; Giuseppe Re; Luca Trevisan 001 (CoRR, 2021)

Introducing The Theory Blogs Column. - Luca Trevisan 001 (Bull. EATCS, 2021)

Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming. - Charles Carlson 002; Alexandra Kolla; Ray Li; Nitya Mani; Benny Sudakov; Luca Trevisan 001 (SIAM J. Discret. Math., 2021)

Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models. - Flavio Chierichetti; Alessandro Panconesi; Giuseppe Re; Luca Trevisan 001 (AISTATS, 2022)

Percolation and Epidemic Processes in One-Dimensional Small-World Networks - (Extended Abstract). - Luca Becchetti; Andrea Clementi; Riccardo Denni; Francesco Pasquale; Luca Trevisan 001; Isabella Ziccardi (LATIN, 2022)

Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification. - Antares Chen; Jonathan Shi; Luca Trevisan 001 (SODA, 2022)

On the Multidimensional Random Subset Sum Problem. - Luca Becchetti; Arthur Carvalho Walraven da Cunha; Andrea Clementi; Francesco D'Amore 001; Hicham Lesfari; Emanuele Natale; Luca Trevisan 001 (CoRR, 2022)

Near-Optimal NP-Hardness of Approximating Max k-CSPR. - Pasin Manurangsi; Preetum Nakkiran; Luca Trevisan 001 (Adv. Math. Commun., 2022)

A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. - Tommaso d'Orsi; Luca Trevisan 001 (CCC, 2023)

On the Role of Memory in Robust Opinion Dynamics. - Luca Becchetti; Andrea Clementi; Amos Korman; Francesco Pasquale; Luca Trevisan 001; Robin Vacus (IJCAI, 2023)

Expansion and flooding in dynamic random networks with node churn. - Luca Becchetti; Andrea Clementi; Francesco Pasquale; Luca Trevisan 001; Isabella Ziccardi (Random Struct. Algorithms, 2023)

The Minority Dynamics and the Power of Synchronicity. - Luca Becchetti; Andrea Clementi; Francesco Pasquale; Luca Trevisan 001; Robin Vacus; Isabella Ziccardi (SODA, 2024)

New SDP Roundings and Certifiable Approximation for Cubic Optimization. - Jun-Ting Hsieh; Pravesh K. Kothari; Lucas Pesenti; Luca Trevisan 001 (SODA, 2024)

Bond percolation in small-world graphs with power-law distribution. - Luca Becchetti; Andrea Clementi; Francesco Pasquale; Luca Trevisan 001; Isabella Ziccardi (Theor. Comput. Sci., 2024)