Theoretical Comp. Sci. » Complexity » Derandomization

Unconditional derandomization of Arthur-Merlin games ★★★

Author(s): Shaltiel; Umans

Problem   Prove unconditionally that $ \mathcal{AM} $ $ \subseteq $ $ \Sigma_2 $.

Keywords: Arthur-Merlin; Hitting Sets; unconditional

Posted by ormeir
updated July 16th, 2007
add new comment
Theoretical Comp. Sci. » Coding Theory

The robustness of the tensor product ★★★

Author(s): Ben-Sasson; Sudan

Problem   Given two codes $ R,C $, their Tensor Product $ R \otimes C $ is the code that consists of the matrices whose rows are codewords of $ R $ and whose columns are codewords of $ C $. The product $ R \otimes C $ is said to be robust if whenever a matrix $ M $ is far from $ R \otimes C $, the rows (columns) of $ M $ are far from $ R $ ($ C $, respectively).

The problem is to give a characterization of the pairs $ R,C $ whose tensor product is robust.

Keywords: codes; coding; locally testable; robustness

Posted by ormeir
updated February 17th, 2010
4 comments
Graph Theory » Coloring » Labeling

Graceful Tree Conjecture ★★★

Author(s):

Conjecture   All trees are graceful

Keywords: combinatorics; graceful labeling

Posted by kintali
updated November 29th, 2020
13 comments
Graph Theory » Coloring » Homomorphisms

Weak pentagon problem ★★

Author(s): Samal

Conjecture   If $ G $ is a cubic graph not containing a triangle, then it is possible to color the edges of $ G $ by five colors, so that the complement of every color class is a bipartite graph.

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

Posted by Robert Samal
updated July 13th, 2007
add new comment