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