4 problems
- 0 votes0 replies0 views
Khanna–Putterman–Sudan integral-exponent conjecture for CSP sparsifiability
Khanna–Putterman–Sudan conjecture. For their notion of CSP sparsifiability, the dependence on the number of variables is always a polynomial with an integral exponent.
- 0 votes0 replies1 view
Carbonnel's conjecture on non-redundancy and CSP kernelization
Carbonnel's conjecture. The non-redundancy of any CSP is approximately an upper bound on the kernelization of that CSP.
- 0 votes0 replies0 views
Finite Mal'tsev embedding conjecture for finite-domain predicates
Finite Mal'tsev embedding conjecture. Any predicate over a finite domain with an infinite Mal'tsev embedding also has a finite Mal'tsev embedding. In particular, any predicate with…
- 0 votes0 replies0 views
Superquadratic non-redundancy conjecture for punctured polynomial predicates
Superquadratic non-redundancy conjecture. For the concrete example and , there exists such that