Lars Engebretsen

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2008

More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP.

Lars Engebretsen, Jonas Holmerin

Random Struct. Algorithms, 2008

2007

Bipartite multigraphs with expander-like properties.

Lars Engebretsen

Discret. Appl. Math., 2007

2006

Platform-independent code conversion within the C++ locale framework.

Lars Engebretsen

Softw. Pract. Exp., 2006

Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.

Lars Engebretsen, Madhu Sudan

Networks, 2006

TSP with bounded metrics.

Lars Engebretsen, Marek Karpinski

J. Comput. Syst. Sci., 2006

2004

Inapproximability results for equations over finite groups.

Lars Engebretsen, Jonas Holmerin, Alexander Russell

Theor. Comput. Sci., 2004

The Nonapproximability of Non-Boolean Predicates.

Lars Engebretsen

SIAM J. Discret. Math., 2004

Simplified tight analysis of Johnson's algorithm.

Lars Engebretsen

Inf. Process. Lett., 2004

2003

Towards optimal lower bounds for clique and chromatic number.

Lars Engebretsen, Jonas Holmerin

Theor. Comput. Sci., 2003

2002

Property testers for dense constraint satisfaction programs on finite domains.

Gunnar Andersson, Lars Engebretsen

Random Struct. Algorithms, 2002

Is Constraint Satisfaction Over Two Variables Always Easy?

Lars Engebretsen, Venkatesan Guruswami

Electron. Colloquium Comput. Complex., 2002

Three-Query PCPs with Perfect Completeness over non-Boolean Domains

Lars Engebretsen, Jonas Holmerin

Electron. Colloquium Comput. Complex., 2002

Harmonic broadcasting is optimal.

Lars Engebretsen, Madhu Sudan

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Derandomized dimensionality reduction with applications.

Lars Engebretsen, Piotr Indyk, Ryan O'Donnell

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.

Gunnar Andersson, Lars Engebretsen, Johan Håstad

J. Algorithms, 2001

The Non-approximability of Non-Boolean Predicates.

Lars Engebretsen

Proceedings of the Approximation, 2001

Using easy optimization problems to solve hard ones.

Lars Engebretsen

Proceedings of the Classical and New Paradigms of Computation and their Complexity Hierarchies, 2001

2000

Approximation Hardness of TSP with Bounded Metrics

Lars Engebretsen, Marek Karpinski

Electron. Colloquium Comput. Complex., 2000

Lower Bounds for non-Boolean Constraint Satisfaction

Lars Engebretsen

Electron. Colloquium Comput. Complex., 2000

Clique Is Hard to Approximate within <i>n</i>^{1-<i>o</i>(1)}.

Lars Engebretsen, Jonas Holmerin

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>.

Gunnar Andersson, Lars Engebretsen, Johan Håstad

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Better Approximation Algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT.

Gunnar Andersson, Lars Engebretsen

Inf. Process. Lett., 1998

An Explicit Lower Bound for TSP with Distances One and Two

Lars Engebretsen

Electron. Colloquium Comput. Complex., 1998

Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems.

Gunnar Andersson, Lars Engebretsen

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

Gunnar Andersson, Lars Engebretsen

Electron. Colloquium Comput. Complex., 1997