Lars Engebretsen

Discret. Appl. Math., 2007

2006

Platform-independent code conversion within the C++ locale framework.

[BibT_eX]

[DOI]

Softw. Pract. Exp., 2006

Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.

[BibT_eX]

[DOI]

Madhu Sudan

Networks, 2006

TSP with bounded metrics.

[BibT_eX]

[DOI]

Marek Karpinski

J. Comput. Syst. Sci., 2006

2005

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

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

2004

The Nonapproximability of Non-Boolean Predicates.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2004

Simplified tight analysis of Johnson's algorithm.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

2003

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

[BibT_eX]

[DOI]

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

2002

Property testers for dense constraint satisfaction programs on finite domains.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2002

Harmonic broadcasting is optimal.

[BibT_eX]

[DOI]

Madhu Sudan

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Derandomized dimensionality reduction with applications.

[BibT_eX]

[DOI]

Piotr Indyk

Ryan O'Donnell

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Is Constraint Satisfaction Over Two Variables Always Easy?

[BibT_eX]

[DOI]

Venkatesan Guruswami

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Inapproximability Results for Equations over Finite Groups.

[BibT_eX]

[DOI]

Alexander Russell

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

2001

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p.

[BibT_eX]

[DOI]

Johan Håstad

J. Algorithms, 2001

Towards Optimal Lower Bounds For Clique and Chromatic Number

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

The Non-approximability of Non-Boolean Predicates.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

Approximation Hardness of TSP with Bounded Metrics.

[BibT_eX]

[DOI]

Marek Karpinski

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Using easy optimization problems to solve hard ones.

[BibT_eX]

[DOI]

Proceedings of the Classical and New Paradigms of Computation and their Complexity Hierarchies, 2001

2000

Lower Bounds for non-Boolean Constraint Satisfaction

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

Clique Is Hard to Approximate within n1-o(1).

[BibT_eX]

[DOI]

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

1999

An Explicit Lower Bound for TSP with Distances One and Two.

[BibT_eX]

[DOI]

Proceedings of the STACS 99, 1999

A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p.

[BibT_eX]

[DOI]

Johan Håstad

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Better Approximation Algorithms for SET SPLITTING and NOT-ALL-EQUAL SAT.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1998

Sampling Methods Applied to Dense Instances of Non-Boolean Optimization Problems.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

1997

Better Approximation Algorithms and Tighter Analysis for Set Splitting and Not-All-Equal Sat

[BibT_eX]

[DOI]