| 2008 |
|---|
| 35 | EE | Lars Engebretsen,
Jonas Holmerin:
More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP.
Random Struct. Algorithms 33(4): 497-514 (2008) |
| 2007 |
|---|
| 34 | EE | Lars Engebretsen:
Bipartite multigraphs with expander-like properties.
Discrete Applied Mathematics 155(13): 1667-1677 (2007) |
| 2006 |
|---|
| 33 | EE | Lars Engebretsen,
Marek Karpinski:
TSP with bounded metrics.
J. Comput. Syst. Sci. 72(4): 509-546 (2006) |
| 32 | EE | Lars Engebretsen,
Madhu Sudan:
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.
Networks 47(3): 172-177 (2006) |
| 31 | EE | Lars Engebretsen:
Platform-independent code conversion within the C++ locale framework.
Softw., Pract. Exper. 36(15): 1643-1654 (2006) |
| 2005 |
|---|
| 30 | EE | Lars Engebretsen,
Jonas Holmerin:
More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP.
STACS 2005: 194-205 |
| 29 | EE | Lars Engebretsen,
Jonas Holmerin:
Three-query PCPs with perfect completeness over non-Boolean domains.
Random Struct. Algorithms 27(1): 46-75 (2005) |
| 2004 |
|---|
| 28 | EE | Lars Engebretsen:
Simplified tight analysis of Johnson's algorithm.
Inf. Process. Lett. 92(4): 207-210 (2004) |
| 27 | EE | Lars Engebretsen,
Venkatesan Guruswami:
Is constraint satisfaction over two variables always easy?
Random Struct. Algorithms 25(2): 150-178 (2004) |
| 26 | EE | Lars Engebretsen:
The Nonapproximability of Non-Boolean Predicates.
SIAM J. Discrete Math. 18(1): 114-129 (2004) |
| 25 | EE | Lars Engebretsen,
Jonas Holmerin,
Alexander Russell:
Inapproximability results for equations over finite groups.
Theor. Comput. Sci. 312(1): 17-45 (2004) |
| 2003 |
|---|
| 24 | EE | Lars Engebretsen,
Jonas Holmerin:
Three-Query PCPs with Perfect Completeness over non-Boolean Domains.
IEEE Conference on Computational Complexity 2003: 284-299 |
| 23 | EE | Lars Engebretsen:
An Explicit Lower Bound for TSP with Distances One and Two.
Algorithmica 35(4): 301-318 (2003) |
| 22 | EE | Lars Engebretsen,
Jonas Holmerin:
Towards optimal lower bounds for clique and chromatic number.
Theor. Comput. Sci. 1-3(299): 537-584 (2003) |
| 2002 |
|---|
| 21 | EE | Lars Engebretsen,
Jonas Holmerin,
Alexander Russell:
Inapproximability Results for Equations over Finite Groups.
ICALP 2002: 73-84 |
| 20 | EE | Lars Engebretsen,
Venkatesan Guruswami:
Is Constraint Satisfaction Over Two Variables Always Easy?
RANDOM 2002: 224-238 |
| 19 | EE | Lars Engebretsen,
Madhu Sudan:
Harmonic broadcasting is optimal.
SODA 2002: 431-432 |
| 18 | EE | Lars Engebretsen,
Piotr Indyk,
Ryan O'Donnell:
Derandomized dimensionality reduction with applications.
SODA 2002: 705-712 |
| 17 | EE | Lars Engebretsen,
Jonas Holmerin,
Alexander Russell:
Inapproximability Results for Equations over Finite Groups
Electronic Colloquium on Computational Complexity (ECCC)(030): (2002) |
| 16 | EE | Lars Engebretsen,
Jonas Holmerin:
Three-Query PCPs with Perfect Completeness over non-Boolean Domains
Electronic Colloquium on Computational Complexity (ECCC)(040): (2002) |
| 15 | EE | Lars Engebretsen,
Venkatesan Guruswami:
Is Constraint Satisfaction Over Two Variables Always Easy?
Electronic Colloquium on Computational Complexity (ECCC)(053): (2002) |
| 14 | EE | Gunnar Andersson,
Lars Engebretsen:
Property testers for dense constraint satisfaction programs on finite domains.
Random Struct. Algorithms 21(1): 14-32 (2002) |
| 2001 |
|---|
| 13 | EE | Lars Engebretsen,
Marek Karpinski:
Approximation Hardness of TSP with Bounded Metrics.
ICALP 2001: 201-212 |
| 12 | EE | Lars Engebretsen:
The Non-approximability of Non-Boolean Predicates.
RANDOM-APPROX 2001: 241-248 |
| 11 | EE | Lars Engebretsen,
Jonas Holmerin:
Towards Optimal Lower Bounds For Clique and Chromatic Number
Electronic Colloquium on Computational Complexity (ECCC) 8(3): (2001) |
| 10 | | 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): 162-204 (2001) |
| 2000 |
|---|
| 9 | EE | Lars Engebretsen,
Jonas Holmerin:
Clique Is Hard to Approximate within n1-o(1).
ICALP 2000: 2-12 |
| 8 | EE | Lars Engebretsen:
Lower Bounds for non-Boolean Constraint Satisfaction
Electronic Colloquium on Computational Complexity (ECCC) 7(42): (2000) |
| 7 | EE | Lars Engebretsen,
Marek Karpinski:
Approximation Hardness of TSP with Bounded Metrics
Electronic Colloquium on Computational Complexity (ECCC) 7(89): (2000) |
| 1999 |
|---|
| 6 | EE | Gunnar Andersson,
Lars Engebretsen,
Johan Håstad:
A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p.
SODA 1999: 41-50 |
| 5 | EE | Lars Engebretsen:
An Explicit Lower Bound for TSP with Distances One and Two.
STACS 1999: 373-382 |
| 1998 |
|---|
| 4 | EE | Gunnar Andersson,
Lars Engebretsen:
Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems.
RANDOM 1998: 357-368 |
| 3 | EE | Lars Engebretsen:
An Explicit Lower Bound for TSP with Distances One and Two
Electronic Colloquium on Computational Complexity (ECCC) 5(46): (1998) |
| 2 | EE | Gunnar Andersson,
Lars Engebretsen:
Better Approximation Algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT.
Inf. Process. Lett. 65(6): 305-311 (1998) |
| 1997 |
|---|
| 1 | EE | Gunnar Andersson,
Lars Engebretsen:
Better Approximation Algorithms and Tighter Analysis for Set Splitting and Not-All-Equal Sat
Electronic Colloquium on Computational Complexity (ECCC) 4(22): (1997) |
