Luca Trevisan

According to our database1, Luca Trevisan authored at least 220 papers between 1994 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs.
CoRR, 2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs.
CoRR, 2019

Optimal Lower Bounds for Sketching Graph Cuts.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Finding a Bounded-Degree Expander Inside a Dense One.
CoRR, 2018

A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs.
CoRR, 2018

A New Algorithm for the Robust Semi-random Independent Set Problem.
CoRR, 2018

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems.
CoRR, 2018

Consensus Needs Broadcast in Noiseless Models but can be Exponentially Easier in the Presence of Noise.
CoRR, 2018

An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Average Whenever You Meet: Opportunistic Protocols for Community Detection.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut.
Proceedings of the Approximation, 2018

2017
Simple dynamics for plurality consensus.
Distributed Computing, 2017

Optimal Lower Bounds for Sketching Graph Cuts.
CoRR, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
CoRR, 2017

An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification.
CoRR, 2017

Friend or Foe? Population Protocols can perform Community Detection.
CoRR, 2017

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Find Your Place: Simple Distributed Algorithms for Community Detection.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016
Learning Heavy Fourier Coefficients of Boolean Functions.
Encyclopedia of Algorithms, 2016

Almost Optimal Local Graph Clustering Using Evolving Sets.
J. ACM, 2016

An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs.
CoRR, 2016

Approximation of non-boolean 2CSP.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Stabilizing Consensus with Many Opinions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Near-Optimal UGC-hardness of Approximating Max k-CSP_R.
Proceedings of the Approximation, 2016

2015
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.
Theory of Computing, 2015

Quantum lower bound for inverting a permutation with advice.
Quantum Information & Computation, 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Information spreading in dynamic graphs.
Distributed Computing, 2015

Near-Optimal UGC-hardness of Approximating Max k-CSP_R.
CoRR, 2015

Approximation of non-boolean 2CSP.
CoRR, 2015

Find Your Place: Simple Distributed Algorithms for Community Detection.
CoRR, 2015

Stabilizing Consensus with Many Opinions.
CoRR, 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.
CoRR, 2015

Unique Games on the Hypercube.
Chicago J. Theor. Comput. Sci., 2015

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree.
Proceedings of the Approximation, 2015

2014
On the One-Way Function Candidate Proposed by Goldreich.
TOCT, 2014

Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).
SIAM J. Comput., 2014

Multiway Spectral Partitioning and Higher-Order Cheeger Inequalities.
J. ACM, 2014

Quantum lower bound for inverting a permutation with advice.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Quantum lower bound for inverting a permutation with advice.
CoRR, 2014

Unique Games on the Hypercube.
CoRR, 2014

Simple dynamics for plurality consensus.
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, 2014

Partitioning into Expanders.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

2013
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank
CoRR, 2013

Is Cheeger-type Approximation Possible for Nonuniform Sparsest Cut?
CoRR, 2013

Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
CoRR, 2013

Partitioning into Expanders.
CoRR, 2013

Simple Dynamics for Majority Consensus.
CoRR, 2013

Improved Cheeger's inequality: analysis of spectral partitioning algorithms through higher order spectral gap.
Proceedings of the Symposium on Theory of Computing Conference, 2013

A Derandomized Switching Lemma and an Improved Derandomization of AC0.
Proceedings of the 28th Conference on Computational Complexity, 2013

A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012
Max Cut and the Smallest Eigenvalue.
SIAM J. Comput., 2012

A Derandomized Switching Lemma and an Improved Derandomization of AC0.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Better pseudorandom generators from milder pseudorandom restrictions.
Electronic Colloquium on Computational Complexity (ECCC), 2012

On the One-Way Function Candidate Proposed by Goldreich.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Pseudorandomness and derandomization.
ACM Crossroads, 2012

A Universal upper bound on Graph Diameter based on Laplacian Eigenvalues
CoRR, 2012

A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
CoRR, 2012

Better Pseudorandom Generators from Milder Pseudorandom Restrictions
CoRR, 2012

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
CoRR, 2012

Multi-way spectral partitioning and higher-order cheeger inequalities.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Information spreading in dynamic graphs.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Better Pseudorandom Generators from Milder Pseudorandom Restrictions.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Approximating the Expansion Profile and Almost Optimal Local Graph Clustering.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
Multi-way spectral partitioning and higher-order Cheeger inequalities
CoRR, 2011

Information Spreading in Dynamic Graphs
CoRR, 2011

Dense Model Theorems and Their Applications.
Proceedings of the Theory of Cryptography - 8th Theory of Cryptography Conference, 2011

From Logarithmic Advice to Single-Bit Advice.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010
The Program-Enumeration Bottleneck in Average-Case Complexity Theory.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Time Space Tradeoffs for Attacks against One-Way Functions and PRGs.
Proceedings of the Advances in Cryptology, 2010

The Program-Enumeration Bottleneck in Average-Case Complexity Theory.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

Improved Pseudorandom Generators for Depth 2 Circuits.
Proceedings of the Approximation, 2010

2009
Guest column: additive combinatorics and theoretical computer science.
SIGACT News, 2009

Gowers Uniformity, Influence of Variables, and PCPs.
SIAM J. Comput., 2009

Non-uniform attacks against one-way functions and PRGs.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Improved Pseudorandom Generators for Depth 2 Circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Foreword.
Algorithmica, 2009

Goldreich's One-Way Function Candidate and Myopic Backtracking Algorithms.
Proceedings of the Theory of Cryptography, 6th Theory of Cryptography Conference, 2009

Max cut and the smallest eigenvalue.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Pseudorandom Bit Generators That Fool Modular Sums.
Proceedings of the Approximation, 2009

Extractors Using Hardness Amplification.
Proceedings of the Approximation, 2009

2008
Approximation Algorithms for Unique Games.
Theory of Computing, 2008

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Dense Subsets of Pseudorandom Sets.
Electronic Colloquium on Computational Complexity (ECCC), 2008

Max Cut and the Smallest Eigenvalue
CoRR, 2008

Average-case Complexity.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Dense Subsets of Pseudorandom Sets.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Pseudorandomness and Average-Case Complexity Via Uniform Reductions.
Computational Complexity, 2007

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Fun with Sub-linear Time Algorithms.
Proceedings of the Fun with Algorithms, 4th International Conference, 2007

Amplifying Collision Resistance: A Complexity-Theoretic Treatment.
Proceedings of the Advances in Cryptology, 2007

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006
On Worst-Case to Average-Case Reductions for NP Problems.
SIAM J. Comput., 2006

On epsilon-biased generators in NC0.
Random Struct. Algorithms, 2006

Average-Case Complexity.
Foundations and Trends in Theoretical Computer Science, 2006

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.
Electronic Colloquium on Computational Complexity (ECCC), 2006

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Pseudorandomness and Combinatorial Constructions
Electronic Colloquium on Computational Complexity (ECCC), 2006

Average-Case Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Average-Case Complexity
CoRR, 2006

Pseudorandomness and Combinatorial Constructions
CoRR, 2006

Lower bounds for linear locally decodable codes and private information retrieval.
Computational Complexity, 2006

Gowers uniformity, influence of variables, and PCPs.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Pseudorandom walks on regular digraphs and the RL vs. L problem.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005
The approximability of non-Boolean satisfiability problems and restricted integer programming.
Theor. Comput. Sci., 2005

Bounds on the Efficiency of Generic Cryptographic Constructions.
SIAM J. Comput., 2005

Approximating the Minimum Spanning Tree Weight in Sublinear Time.
SIAM J. Comput., 2005

Approximating Succinct MaxSat.
J. Log. Comput., 2005

Gowers Uniformity, Influence of Variables, and PCPs
Electronic Colloquium on Computational Complexity (ECCC), 2005

Approximation Algorithms for Unique Games
Electronic Colloquium on Computational Complexity (ECCC), 2005

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Electronic Colloquium on Computational Complexity (ECCC), 2005

On Worst-Case to Average-Case Reductions for NP Problems
Electronic Colloquium on Computational Complexity (ECCC), 2005

Compression of Samplable Sources
Electronic Colloquium on Computational Complexity (ECCC), 2005

Gowers Uniformity, Influence of Variables, and PCPs
CoRR, 2005

Compression of Samplable Sources.
Computational Complexity, 2005

On Hardness Amplification of One-Way Functions.
Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

On uniform amplification of hardness in NP.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Hierarchies for semantic classes.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Approximation Algorithms for Unique Games.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

The Complexity of Making Unique Choices: Approximating 1-in- k SAT.
Proceedings of the Approximation, 2005

2004
On Local Versus Global Satisfiability.
SIAM J. Discrete Math., 2004

Promise Hierarchies
Electronic Colloquium on Computational Complexity (ECCC), 2004

From logarithmic advice to single-bit advice
Electronic Colloquium on Computational Complexity (ECCC), 2004

Inapproximability of Combinatorial Optimization Problems
Electronic Colloquium on Computational Complexity (ECCC), 2004

Some Applications of Coding Theory in Computational Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2004

Some Applications of Coding Theory in Computational Complexity
CoRR, 2004

Inapproximability of Combinatorial Optimization Problems
CoRR, 2004

Notions of Reducibility between Cryptographic Primitives.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument.
Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Compression of Samplable Sources.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Lower Bounds for Testing Bipartiteness in Dense Graphs.
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

A Note on Approximate Counting for k-DNF.
Proceedings of the Approximation, 2004

Pseudorandomness - Part II.
Proceedings of the Computational Complexity Theory., 2004

2003
Three theorems regarding testing graph properties.
Random Struct. Algorithms, 2003

On epsilon-Biased Generators in NC0
Electronic Colloquium on Computational Complexity (ECCC), 2003

List Decoding Using the XOR Lemma
Electronic Colloquium on Computational Complexity (ECCC), 2003

An epsilon-Biased Generator in NC0
Electronic Colloquium on Computational Complexity (ECCC), 2003

List-Decoding Using The XOR Lemma.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

On e-Biased Generators in NC0.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

On Worst-Case to Average-Case Reductions for NP Problems.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Error-Correcting Codes in Complexity Theory.
Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002
A Note on Deterministic Approximate Counting for k-DNF
Electronic Colloquium on Computational Complexity (ECCC), 2002

Lower Bounds for Testing Bipartiteness in Dense Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2002

Counting Distinct Elements in a Data Stream.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Pseudorandomness and Average-Case Complexity via Uniform Reductions.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Streaming Computation of Combinatorial Objects.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
Pseudorandom Generators without the XOR Lemma.
J. Comput. Syst. Sci., 2001

Extractors and pseudorandom generators.
J. ACM, 2001

On Weighted vs Unweighted Versions of Combinatorial Optimization Problems.
Inf. Comput., 2001

Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval
Electronic Colloquium on Computational Complexity (ECCC), 2001

Three Theorems regarding Testing Graph Properties.
Electronic Colloquium on Computational Complexity (ECCC), 2001

Approximating layout problems on random graphs.
Discrete Mathematics, 2001

Non-approximability results for optimization problems on bounded degree instances.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Error-Correcting Codes and Pseudorandom Projections.
Proceedings of the Approximation, 2001

Approximating the Minimum Spanning Tree Weight in Sublinear Time.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Three Theorems Regarding Testing Graph Properties.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
A complexity analysis of bisimilarity for value-passing processes.
Theor. Comput. Sci., 2000

Gadgets, Approximation, and Linear Programming.
SIAM J. Comput., 2000

When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree.
SIAM J. Comput., 2000

The Approximability of Constraint Satisfaction Problems.
SIAM J. Comput., 2000

On Approximation Scheme Preserving Reducibility and Its Applications.
Theory Comput. Syst., 2000

Lower Bounds on the Efficiency of Generic Cryptographic Constructions.
IACR Cryptology ePrint Archive, 2000

Lower Bounds on the Efficiency of Generic Cryptographic Constructions
Electronic Colloquium on Computational Complexity (ECCC), 2000

Interactive and probabilistic proof-checking.
Ann. Pure Appl. Logic, 2000

Approximating Satisfiable Satisfiability Problems.
Algorithmica, 2000

Erratum: A Correction to "Parallel Approximation Algorithms by Positive Linear Programming".
Algorithmica, 2000

A PCP characterization of NP with optimal amortized query complexity.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

On the efficiency of local decoding procedures for error-correcting codes.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Extracting Randomness from Samplable Distributions.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Lower Bounds on the Efficiency of Generic Cryptographic Constructions.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

A Survey of Optimal PCP Characterizations of NP.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999
Max NP-completeness Made Easy.
Theor. Comput. Sci., 1999

Improved Non-Approximability Results for Minimum Vertex Cover with Density Constraints.
Theor. Comput. Sci., 1999

Structure in Approximation Classes.
SIAM J. Comput., 1999

Weak Random Sources, Hitting Sets, and BPP Simulations.
SIAM J. Comput., 1999

Construction of Extractors Using Pseudo-Random Generators (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Pseudorandom Generators without the XOR Lemma (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
The Parallel Complexity of Positive Linear Programming.
Parallel Processing Letters, 1998

A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms.
J. Comb. Optim., 1998

Pseudorandom generators without the XOR Lemma
Electronic Colloquium on Computational Complexity (ECCC), 1998

Constructions of Near-Optimal Extractors Using Pseudo-Random Generators
Electronic Colloquium on Computational Complexity (ECCC), 1998

Probabilistically checkable proofs with low amortized query complexity
Electronic Colloquium on Computational Complexity (ECCC), 1998

A tight characterization of NP with 3 query PCPs
Electronic Colloquium on Computational Complexity (ECCC), 1998

Recycling Queries in PCPs and in Linearity Tests
Electronic Colloquium on Computational Complexity (ECCC), 1998

Recent Advances Towards Proving P = BPP.
Bulletin of the EATCS, 1998

Parallel Approximation Algorithms by Positive Linear Programming.
Algorithmica, 1998

Recycling Queries in PCPs and in Linearity Tests (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming.
Proceedings of the STACS 98, 1998

Probabilistically Checkable Proofs with Low Amortized Query Complexity.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

A Tight Characterization of NP with 3 Query PCPs.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
On the Efficiency of Polynomial Time Approximation Schemes.
Inf. Process. Lett., 1997

MAX NP-Completeness Made Easy
Electronic Colloquium on Computational Complexity (ECCC), 1997

On Local versus Global Satisfiability
Electronic Colloquium on Computational Complexity (ECCC), 1997

Weak Random Sources, Hitting Sets, and BPP Simulations
Electronic Colloquium on Computational Complexity (ECCC), 1997

On the Efficiency of Polynomial Time Approximation Schemes
Electronic Colloquium on Computational Complexity (ECCC), 1997

When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Weak Random Sources, Hitting Sets, and BPP Simulations.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Approximating Satisfiable Satisfiability Problems (Extended Abstract).
Proceedings of the Algorithms, 1997

A case study of de-randomization methods for combinatorial approximation algorithms.
Proceedings of the Network Design: Connectivity and Facilities Location, 1997

Constraint Satisfaction: The Approximability of Minimization Problems.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
On the Distributed Decision-Making Complexity of the Minimum Vertex Cover Problem.
ITA, 1996

A Note on Minimum-Area Upward Drawing of Complete and Fibonacci Trees.
Inf. Process. Lett., 1996

Structure in Approximation Classes
Electronic Colloquium on Computational Complexity (ECCC), 1996

Constraint satisfaction: The approximability of minimization problems.
Electronic Colloquium on Computational Complexity (ECCC), 1996

On the Approximability of the Multi-dimensional Euclidean TSP
Electronic Colloquium on Computational Complexity (ECCC), 1996

Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints
Electronic Colloquium on Computational Complexity (ECCC), 1996

Bisimilarity Problems Requiring Exponential Time.
Proceedings of the Mathematical Foundations of Computer Science 1996, 1996

To Weight or Not to Weight: Where is the Question?
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Gadgets, Approximation, and Linear Programming (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Positive Linear Programming, Parallel Approximation and PCP's.
Proceedings of the Algorithms, 1996

Improved Non-approximability Results for Vertex Cover with Density Constraints.
Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995
On the Complexity of Bisimilarity for Value-Passing Processes (Extended Abstract).
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

Structure in Approximation Classes (Extended Abstract).
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994
Minimum Vertex Cover, Distributed Decision-Making, and Communication Complexity (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

On Approximation Scheme Preserving Reducability and Its Applications.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994


  Loading...