Lars Engebretsen

36 papers A* 6A 3Journal 23Unranked 4
YearRankTypeTitle / Venue / Authors
2008 J jnl
More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP.
Random Struct. Algorithms
Lars Engebretsen, Jonas Holmerin
2007 J jnl
Bipartite multigraphs with expander-like properties.
Discret. Appl. Math.
Lars Engebretsen
2006 J jnl
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.
Networks
Lars Engebretsen, Madhu Sudan
2006 J jnl
Platform-independent code conversion within the C++ locale framework.
Softw. Pract. Exp.
Lars Engebretsen
2006 J jnl
TSP with bounded metrics.
J. Comput. Syst. Sci.
Lars Engebretsen, Marek Karpinski
2005 A conf
More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP.
STACS
Lars Engebretsen, Jonas Holmerin
2005 J jnl
Three-query PCPs with perfect completeness over non-Boolean domains.
Random Struct. Algorithms
Lars Engebretsen, Jonas Holmerin
2004 J jnl
Inapproximability results for equations over finite groups.
Theor. Comput. Sci.
Lars Engebretsen, Jonas Holmerin, Alexander Russell
2004 J jnl
Is constraint satisfaction over two variables always easy?
Random Struct. Algorithms
Lars Engebretsen, Venkatesan Guruswami
2004 J jnl
Simplified tight analysis of Johnson's algorithm.
Inf. Process. Lett.
Lars Engebretsen
2004 J jnl
The Nonapproximability of Non-Boolean Predicates.
SIAM J. Discret. Math.
Lars Engebretsen
2003 J jnl
An Explicit Lower Bound for TSP with Distances One and Two.
Algorithmica
Lars Engebretsen
2003 A conf
Three-Query PCPs with Perfect Completeness over non-Boolean Domains.
CCC
Lars Engebretsen, Jonas Holmerin
2003 J jnl
Towards optimal lower bounds for clique and chromatic number.
Theor. Comput. Sci.
Lars Engebretsen, Jonas Holmerin
2002 A* conf
Derandomized dimensionality reduction with applications.
SODA
Lars Engebretsen, Piotr Indyk, Ryan O'Donnell
2002 A* conf
Harmonic broadcasting is optimal.
SODA
Lars Engebretsen, Madhu Sudan
2002 J jnl
Inapproximability Results for Equations over Finite Groups
Electron. Colloquium Comput. Complex.
Lars Engebretsen, Jonas Holmerin, Alexander Russell
2002 A* conf
Inapproximability Results for Equations over Finite Groups.
ICALP
Lars Engebretsen, Jonas Holmerin, Alexander Russell
2002 — conf
Is Constraint Satisfaction Over Two Variables Always Easy?
RANDOM
Lars Engebretsen, Venkatesan Guruswami
2002 J jnl
Is Constraint Satisfaction Over Two Variables Always Easy?
Electron. Colloquium Comput. Complex.
Lars Engebretsen, Venkatesan Guruswami
2002 J jnl
Property testers for dense constraint satisfaction programs on finite domains.
Random Struct. Algorithms
Gunnar Andersson, Lars Engebretsen
2002 J jnl
Three-Query PCPs with Perfect Completeness over non-Boolean Domains
Electron. Colloquium Comput. Complex.
Lars Engebretsen, Jonas Holmerin
2001 J jnl
A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p.
J. Algorithms
Gunnar Andersson, Lars Engebretsen, Johan Håstad
2001 A* conf
Approximation Hardness of TSP with Bounded Metrics.
ICALP
Lars Engebretsen, Marek Karpinski
2001 — conf
The Non-approximability of Non-Boolean Predicates.
RANDOM-APPROX
Lars Engebretsen
2001 J jnl
Towards Optimal Lower Bounds For Clique and Chromatic Number
Electron. Colloquium Comput. Complex.
Lars Engebretsen, Jonas Holmerin
2001 — conf
Using easy optimization problems to solve hard ones.
FotFS
Lars Engebretsen
2000 J jnl
Approximation Hardness of TSP with Bounded Metrics
Electron. Colloquium Comput. Complex.
Lars Engebretsen, Marek Karpinski
2000 A* conf
Clique Is Hard to Approximate within
ICALP
Lars Engebretsen, Jonas Holmerin
2000 J jnl
Lower Bounds for non-Boolean Constraint Satisfaction
Electron. Colloquium Comput. Complex.
Lars Engebretsen
1999 A* conf
A New Way to Use Semidefinite Programming with Applications to Linear Equations mod
SODA
Gunnar Andersson, Lars Engebretsen, Johan Håstad
1999 A conf
An Explicit Lower Bound for TSP with Distances One and Two.
STACS
Lars Engebretsen
1998 J jnl
An Explicit Lower Bound for TSP with Distances One and Two
Electron. Colloquium Comput. Complex.
Lars Engebretsen
1998 J jnl
Better Approximation Algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT.
Inf. Process. Lett.
Gunnar Andersson, Lars Engebretsen
1998 — conf
Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems.
RANDOM
Gunnar Andersson, Lars Engebretsen
1997 J jnl
Better Approximation Algorithms and Tighter Analysis for Set Splitting and Not-All-Equal Sat
Electron. Colloquium Comput. Complex.
Gunnar Andersson, Lars Engebretsen