Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDLuca Trevisan
Person information
- affiliation: University of California, Berkeley, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[c101]Tommaso d'Orsi, Luca Trevisan:
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. CCC 2023: 27:1-27:16- [c100]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: 29-37 - [c99]Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi:
Bond Percolation in Small-World Graphs with Power-Law Distribution. SAND 2023: 3:1-3:22 - [i92]Luca Becchetti, Andrea E. F. Clementi, Amos Korman, Francesco Pasquale, Luca Trevisan, Robin Vacus:
On the Role of Memory in Robust Opinion Dynamics. CoRR abs/2302.08600 (2023) - [i91]Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan:
New SDP Roundings and Certifiable Approximation for Cubic Optimization. CoRR abs/2310.00393 (2023) - [i90]Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, Isabella Ziccardi:
The Minority Dynamics and the Power of Synchronicity. CoRR abs/2310.13558 (2023) - 2022
- [j56]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): 5466 (2022) - [j55]Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan:
Near-Optimal NP-Hardness of Approximating Max k-CSPR. Theory Comput. 18: 1-29 (2022) - [c98]Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, Luca Trevisan:
Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models. AISTATS 2022: 10852-10880 - [c97]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: 476-492 - [c96]Antares Chen, Jonathan Shi, Luca Trevisan:
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification. SODA 2022: 3693-3731 - [i89]Tommaso d'Orsi, Luca Trevisan:
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. CoRR abs/2204.10881 (2022) - [i88]Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi:
Bond Percolation in Small-World Graphs with Power-Law Distribution. CoRR abs/2205.08774 (2022) - [i87]Luca Becchetti, Arthur Carvalho Walraven da Cunha, Andrea E. F. Clementi, Francesco D'Amore, Hicham Lesfari, Emanuele Natale, Luca Trevisan:
On the Multidimensional Random Subset Sum Problem. CoRR abs/2207.13944 (2022) - 2021
- [j54]Luca Trevisan:
Introducing The Theory Blogs Column. Bull. EATCS 135 (2021) - [j53]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): 1557-1568 (2021) - [c95]Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi:
Expansion and Flooding in Dynamic Random Networks with Node Churn. ICDCS 2021: 976-986 - [i86]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 abs/2103.16398 (2021) - [i85]Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, Luca Trevisan:
Correlation Clustering Reconstruction in Semi-Adversarial Models. CoRR abs/2108.04729 (2021) - 2020
- [j52]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): 772-810 (2020) - [j51]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): 821-864 (2020) - [c94]Luca Trevisan, Stefano Vitturi, Federico Tramarin, Alberto Morato:
An IIoT System to Monitor 3D-Printed Artifacts via LoRaWAN Embedded Sensors. ETFA 2020: 1331-1334 - [c93]Samuel B. Hopkins, Tselil Schramm, Luca Trevisan:
Subexponential LPs Approximate Max-Cut. FOCS 2020: 943-953 - [c92]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: 1-6 - [c91]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: 42:1-42:13 - [c90]Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan:
Lower Bounds for Max-Cut via Semidefinite Programming. LATIN 2020: 479-490 - [c89]Theo McKenzie, Hermish Mehta, Luca Trevisan:
A New Algorithm for the Robust Semi-random Independent Set Problem. SODA 2020: 738-746 - [c88]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Finding a Bounded-Degree Expander Inside a Dense One. SODA 2020: 1320-1336 - [i84]Luca Becchetti, Andrea E. F. Clementi, Francesco Pasquale, Luca Trevisan, Isabella Ziccardi:
Expansion and Flooding in Dynamic Random Networks with Node Churn. CoRR abs/2007.14681 (2020) - [i83]Antares Chen, Jonathan Shi, Luca Trevisan:
Cut Sparsification of the Clique Beyond the Ramanujan Bound. CoRR abs/2008.05648 (2020)
2010 – 2019
- 2019
- [c87]Nikhil Bansal, Ola Svensson, Luca Trevisan:
New Notions and Constructions of Sparsification for Graphs and Hypergraphs. FOCS 2019: 910-928 - [c86]Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan:
Optimal Lower Bounds for Sketching Graph Cuts. SODA 2019: 2565-2569 - [i82]Nikhil Bansal, Ola Svensson, Luca Trevisan:
New Notions and Constructions of Sparsification for Graphs and Hypergraphs. CoRR abs/1905.01495 (2019) - [i81]Jess Banks, Luca Trevisan:
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs. CoRR abs/1907.02539 (2019) - [i80]Samuel B. Hopkins, Tselil Schramm, Luca Trevisan:
Subexponential LPs Approximate Max-Cut. CoRR abs/1911.10304 (2019) - 2018
- [c85]Pasin Manurangsi, Luca Trevisan:
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut. APPROX-RANDOM 2018: 20:1-20:17 - [c84]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: 7:1-7:13 - [c83]Nikhil Srivastava, Luca Trevisan:
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification. SODA 2018: 1306-1315 - [i79]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 abs/1807.05626 (2018) - [i78]Pasin Manurangsi, Luca Trevisan:
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems. CoRR abs/1807.09898 (2018) - [i77]Theo McKenzie, Hermish Mehta, Luca Trevisan:
A New Algorithm for the Robust Semi-random Independent Set Problem. CoRR abs/1808.03633 (2018) - [i76]Charles Carlson, Alexandra Kolla, Luca Trevisan:
A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs. CoRR abs/1810.10044 (2018) - [i75]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Finding a Bounded-Degree Expander Inside a Dense One. CoRR abs/1811.10316 (2018) - 2017
- [j50]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan:
Simple dynamics for plurality consensus. Distributed Comput. 30(4): 293-306 (2017) - [c82]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: 743-754 - [c81]Michele Borassi, Pierluigi Crescenzi, Luca Trevisan:
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. SODA 2017: 920-939 - [c80]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Find Your Place: Simple Distributed Algorithms for Community Detection. SODA 2017: 940-959 - [i74]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Prasad Raghavendra, Luca Trevisan:
Friend or Foe? Population Protocols can perform Community Detection. CoRR abs/1703.05045 (2017) - [i73]Nikhil Srivastava, Luca Trevisan:
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification. CoRR abs/1707.06364 (2017) - [i72]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 abs/1708.04218 (2017) - [i71]Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan:
Optimal Lower Bounds for Sketching Graph Cuts. CoRR abs/1712.10261 (2017) - 2016
- [j49]Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan:
Almost Optimal Local Graph Clustering Using Evolving Sets. J. ACM 63(2): 15:1-15:31 (2016) - [c79]Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan:
Near-Optimal UGC-hardness of Approximating Max k-CSP_R. APPROX-RANDOM 2016: 15:1-15:28 - [c78]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Stabilizing Consensus with Many Opinions. SODA 2016: 620-635 - [c77]Guy Kindler, Alexandra Kolla, Luca Trevisan:
Approximation of non-boolean 2CSP. SODA 2016: 1705-1714 - [r2]Luca Trevisan:
Learning Heavy Fourier Coefficients of Boolean Functions. Encyclopedia of Algorithms 2016: 1078-1081 - [i70]Michele Borassi, Pierluigi Crescenzi, Luca Trevisan:
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. CoRR abs/1604.01445 (2016) - 2015
- [j48]Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan:
Unique Games on the Hypercube. Chic. J. Theor. Comput. Sci. 2015 (2015) - [j47]Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan:
Information spreading in dynamic graphs. Distributed Comput. 28(1): 55-73 (2015) - [j46]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. 15(11&12): 901-913 (2015) - [j45]Shayan Oveis Gharan, Luca Trevisan:
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. Theory Comput. 11: 241-256 (2015) - [c76]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: 110-123 - [i69]Guy Kindler, Alexandra Kolla, Luca Trevisan:
Approximation of non-boolean 2CSP. CoRR abs/1504.00681 (2015) - [i68]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 abs/1505.03424 (2015) - [i67]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Stabilizing Consensus with Many Opinions. CoRR abs/1508.06782 (2015) - [i66]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Luca Trevisan:
Find Your Place: Simple Distributed Algorithms for Community Detection. CoRR abs/1511.03927 (2015) - [i65]Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan:
Near-Optimal UGC-hardness of Approximating Max k-CSP_R. CoRR abs/1511.06558 (2015) - [i64]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. TR15 (2015) - 2014
- [j44]James R. Lee, Shayan Oveis Gharan, Luca Trevisan:
Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities. J. ACM 61(6): 37:1-37:30 (2014) - [j43]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): 255 (2014) - [j42]James Cook, Omid Etesami, Rachel Miller, Luca Trevisan:
On the One-Way Function Candidate Proposed by Goldreich. ACM Trans. Comput. Theory 6(3): 14:1-14:35 (2014) - [c75]Shayan Oveis Gharan, Luca Trevisan:
Partitioning into Expanders. SODA 2014: 1256-1266 - [c74]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan:
Simple dynamics for plurality consensus. SPAA 2014: 247-256 - [i63]Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan:
Unique Games on the Hypercube. CoRR abs/1405.1374 (2014) - [i62]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. CoRR abs/1408.3193 (2014) - [i61]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c73]Shayan Oveis Gharan, Luca Trevisan:
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. APPROX-RANDOM 2013: 303-316 - [c72]Luca Trevisan, Tongke Xue:
A Derandomized Switching Lemma and an Improved Derandomization of AC0. CCC 2013: 242-247 - [c71]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: 11-20 - [e3]T.-H. Hubert Chan, Lap Chi Lau, Luca Trevisan:
Theory and Applications of Models of Computation, 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. Lecture Notes in Computer Science 7876, Springer 2013, ISBN 978-3-642-38235-2 [contents] - [i60]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 abs/1301.5584 (2013) - [i59]Luca Trevisan:
Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut? CoRR abs/1303.2730 (2013) - [i58]Shayan Oveis Gharan, Luca Trevisan:
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank. CoRR abs/1304.2060 (2013) - [i57]Shayan Oveis Gharan, Luca Trevisan:
Partitioning into Expanders. CoRR abs/1309.3223 (2013) - [i56]Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, Luca Trevisan:
Simple Dynamics for Majority Consensus. CoRR abs/1310.2858 (2013) - 2012
- [j41]Luca Trevisan:
Pseudorandomness and derandomization. XRDS 18(3): 27-31 (2012) - [j40]Luca Trevisan:
Max Cut and the Smallest Eigenvalue. SIAM J. Comput. 41(6): 1769-1786 (2012) - [c70]Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Better Pseudorandom Generators from Milder Pseudorandom Restrictions. FOCS 2012: 120-129 - [c69]Shayan Oveis Gharan, Luca Trevisan:
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. FOCS 2012: 187-196 - [c68]Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan:
Information spreading in dynamic graphs. PODC 2012: 37-46 - [c67]James R. Lee, Shayan Oveis Gharan, Luca Trevisan:
Multi-way spectral partitioning and higher-order cheeger inequalities. STOC 2012: 1117-1130 - [i55]Shayan Oveis Gharan, Luca Trevisan:
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering. CoRR abs/1204.2021 (2012) - [i54]Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Better Pseudorandom Generators from Milder Pseudorandom Restrictions. CoRR abs/1210.0049 (2012) - [i53]Shayan Oveis Gharan, Luca Trevisan:
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs. CoRR abs/1212.1831 (2012) - [i52]Shayan Oveis Gharan, Luca Trevisan:
A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues. CoRR abs/1212.2701 (2012) - [i51]James Cook, Omid Etesami, Rachel Miller, Luca Trevisan:
On the One-Way Function Candidate Proposed by Goldreich. Electron. Colloquium Comput. Complex. TR12 (2012) - [i50]Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Better pseudorandom generators from milder pseudorandom restrictions. Electron. Colloquium Comput. Complex. TR12 (2012) - [i49]Luca Trevisan:
A Derandomized Switching Lemma and an Improved Derandomization of AC0. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c66]Luca Trevisan:
Dense Model Theorems and Their Applications. TCC 2011: 55-57 - [p2]Oded Goldreich, Madhu Sudan, Luca Trevisan:
From Logarithmic Advice to Single-Bit Advice. Studies in Complexity and Cryptography 2011: 109-113 - [i48]Andrea E. F. Clementi, Riccardo Silvestri, Luca Trevisan:
Information Spreading in Dynamic Graphs. CoRR abs/1111.0583 (2011) - [i47]James R. Lee, Shayan Oveis Gharan, Luca Trevisan:
Multi-way spectral partitioning and higher-order Cheeger inequalities. CoRR abs/1111.1055 (2011) - 2010
- [c65]Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani:
Improved Pseudorandom Generators for Depth 2 Circuits. APPROX-RANDOM 2010: 504-517 - [c64]Luca Trevisan:
The Program-Enumeration Bottleneck in Average-Case Complexity Theory. CCC 2010: 88-95 - [c63]Anindya De, Luca Trevisan, Madhur Tulsiani:
Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. CRYPTO 2010: 649-665 - [i46]Luca Trevisan:
The Program-Enumeration Bottleneck in Average-Case Complexity Theory. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j39]Chandra Chekuri, Luca Trevisan:
Foreword. Algorithmica 55(1): 111-112 (2009) - [j38]Alex Samorodnitsky, Luca Trevisan:
Gowers Uniformity, Influence of Variables, and PCPs. SIAM J. Comput. 39(1): 323-360 (2009) - [j37]Luca Trevisan:
Guest column: additive combinatorics and theoretical computer science. SIGACT News 40(2): 50-66 (2009) - [c62]Anindya De, Luca Trevisan:
Extractors Using Hardness Amplification. APPROX-RANDOM 2009: 462-475 - [c61]Shachar Lovett, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Bit Generators That Fool Modular Sums. APPROX-RANDOM 2009: 615-630 - [c60]Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. CCC 2009: 126-136 - [c59]Luca Trevisan:
Max cut and the smallest eigenvalue. STOC 2009: 263-272 - [c58]James Cook, Omid Etesami, Rachel Miller, Luca Trevisan:
Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms. TCC 2009: 521-538 - [i45]Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani:
Improved Pseudorandom Generators for Depth 2 Circuits. Electron. Colloquium Comput. Complex. TR09 (2009) - [i44]Anindya De, Luca Trevisan, Madhur Tulsiani:
Non-uniform attacks against one-way functions and PRGs. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j36]Luca Trevisan:
Approximation Algorithms for Unique Games. Theory Comput. 4(1): 111-128 (2008) - [c57]