Jonas Holmerin

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

Collaborative distances:

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

2005

More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP.

Lars Engebretsen, Jonas Holmerin

Proceedings of the STACS 2005, 2005

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

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

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

Lars Engebretsen, Jonas Holmerin

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

2002

Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon.

Jonas Holmerin

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

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

Jonas Holmerin

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

Inapproximability Results for Equations over Finite Groups.

Lars Engebretsen, Jonas Holmerin, Alexander Russell

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

Towards Optimal Lower Bounds For Clique and Chromatic Number

Lars Engebretsen, 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