Jonas Holmerin

According to our database, Jonas Holmerin authored at least 12 papers between 2000 and 2008.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2008

More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP.

Lars Engebretsen, Jonas Holmerin

Random Struct. Algorithms, 2008

2004

Inapproximability results for equations over finite groups.

Lars Engebretsen, Jonas Holmerin, Alexander Russell

Theor. Comput. Sci., 2004

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.

Jonas Holmerin, Subhash Khot

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

2003

Towards optimal lower bounds for clique and chromatic number.

Lars Engebretsen, Jonas Holmerin

Theor. Comput. Sci., 2003

A Strong Inapproximability Gap for a Generalization of Minimum Bisection.

Jonas Holmerin, Subhash Khot

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Three-Query PCPs with Perfect Completeness over non-Boolean Domains

Lars Engebretsen, Jonas Holmerin

Electron. Colloquium Comput. Complex., 2002

Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs.

Jonas Holmerin

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - ε.

Jonas Holmerin

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2-epsilon

Jonas Holmerin

Electron. Colloquium Comput. Complex., 2001

2000

Data Field Haskell.

Jonas Holmerin, Björn Lisper

Proceedings of the 2000 ACM SIGPLAN Workshop on Haskell, 2000

Clique Is Hard to Approximate within <i>n</i>^{1-<i>o</i>(1)}.

Lars Engebretsen, Jonas Holmerin

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Development of Parallel Algorithms in Data Field Haskell (Research Note).

Jonas Holmerin, Björn Lisper

Proceedings of the Euro-Par 2000, Parallel Processing, 6th International Euro-Par Conference, Munich, Germany, August 29, 2000