Lars Engebretsen

Affiliations:
  • Royal Institute of Technology, Stockholm, Sweden


According to our database1, Lars Engebretsen authored at least 25 papers between 1997 and 2008.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2008
More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP.
Random Struct. Algorithms, 2008

2007
Bipartite multigraphs with expander-like properties.
Discret. Appl. Math., 2007

2006
Platform-independent code conversion within the C++ locale framework.
Softw. Pract. Exp., 2006

Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.
Networks, 2006

TSP with bounded metrics.
J. Comput. Syst. Sci., 2006

2004
Inapproximability results for equations over finite groups.
Theor. Comput. Sci., 2004

The Nonapproximability of Non-Boolean Predicates.
SIAM J. Discret. Math., 2004

Simplified tight analysis of Johnson's algorithm.
Inf. Process. Lett., 2004

2003
Towards optimal lower bounds for clique and chromatic number.
Theor. Comput. Sci., 2003

2002
Property testers for dense constraint satisfaction programs on finite domains.
Random Struct. Algorithms, 2002

Is Constraint Satisfaction Over Two Variables Always Easy?
Electron. Colloquium Comput. Complex., 2002

Three-Query PCPs with Perfect Completeness over non-Boolean Domains
Electron. Colloquium Comput. Complex., 2002

Harmonic broadcasting is optimal.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Derandomized dimensionality reduction with applications.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001
A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p.
J. Algorithms, 2001

The Non-approximability of Non-Boolean Predicates.
Proceedings of the Approximation, 2001

Using easy optimization problems to solve hard ones.
Proceedings of the Classical and New Paradigms of Computation and their Complexity Hierarchies, 2001

2000
Approximation Hardness of TSP with Bounded Metrics
Electron. Colloquium Comput. Complex., 2000

Lower Bounds for non-Boolean Constraint Satisfaction
Electron. Colloquium Comput. Complex., 2000

Clique Is Hard to Approximate within <i>n</i><sup>1-<i>o</i>(1)</sup>.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999
A New Way to Use Semidefinite Programming with Applications to Linear Equations mod <i>p</i>.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998
Better Approximation Algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT.
Inf. Process. Lett., 1998

An Explicit Lower Bound for TSP with Distances One and Two
Electron. Colloquium Comput. Complex., 1998

Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

1997
Better Approximation Algorithms and Tighter Analysis for Set Splitting and Not-All-Equal Sat
Electron. Colloquium Comput. Complex., 1997


  Loading...