dblp.uni-trier.dewww.uni-trier.de

Lars Engebretsen

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

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

Coauthor Index

1Gunnar Andersson [1] [2] [4] [6] [10] [14]
2Venkatesan Guruswami [15] [20] [27]
3Johan Håstad [6] [10]
4Jonas Holmerin [9] [11] [16] [17] [21] [22] [24] [25] [29] [30] [35]
5Piotr Indyk [18]
6Marek Karpinski [7] [13] [33]
7Ryan O'Donnell [18]
8Alexander Russell [17] [21] [25]
9Madhu Sudan [19] [32]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)