Lars Engebretsen

Available identifiers

zbMath Open engebretsen.larsMaRDI QIDQ293271

List of research outcomes

Publication	Date of Publication	Type
Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}	2016-06-09	Paper
Simplified tight analysis of Johnson's algorithm	2009-08-27	Paper
More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP	2009-03-04	Paper
Bipartite multigraphs with expander-like properties	2007-09-18	Paper
TSP with bounded metrics	2006-06-30	Paper
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate	2006-06-06	Paper
STACS 2005	2005-12-02	Paper
Three‐query PCPs with perfect completeness over non‐Boolean domains	2005-08-29	Paper
The Nonapproximability of Non-Boolean Predicates	2005-02-28	Paper
Is constraint satisfaction over two variables always easy?	2005-01-12	Paper
https://portal.mardi4nfdi.de/entity/Q4829005	2004-11-29	Paper
https://portal.mardi4nfdi.de/entity/Q4828964	2004-11-29	Paper
Inapproximability results for equations over finite groups	2004-10-27	Paper
https://portal.mardi4nfdi.de/entity/Q4737146	2004-08-11	Paper
https://portal.mardi4nfdi.de/entity/Q4440440	2003-12-17	Paper
An explicit lower bound for TSP with distances one and two	2003-08-19	Paper
Towards optimal lower bounds for clique and chromatic number.	2003-05-25	Paper
A new way of using semidefinite programming with applications to linear equations mod \(p\)	2002-12-10	Paper
https://portal.mardi4nfdi.de/entity/Q4780798	2002-11-21	Paper
https://portal.mardi4nfdi.de/entity/Q4535019	2002-06-12	Paper
Property testers for dense constraint satisfaction programs on finite domains	2002-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q2754129	2001-11-11	Paper
https://portal.mardi4nfdi.de/entity/Q4247205	2000-09-26	Paper
https://portal.mardi4nfdi.de/entity/Q4252269	2000-02-02	Paper

Research outcomes over time

This page was built for person: Lars Engebretsen