Lars Engebretsen

Publication Activity (10 Years)

Years Active: 1997-2008
Publications (10 Years): 0

Publications

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