Recent Activity
Exponential Algorithms for Knapsack ★★
Author(s): Lipton
The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?
Keywords: Algorithm construction; Exponential-time algorithm; Knapsack
Unsolvability of word problem for 2-knot complements ★★★
Author(s): Gordon
Keywords: 2-knot; Computational Complexity; knot theory
Algorithm for graph homomorphisms ★★
Author(s): Fomin; Heggernes; Kratsch
Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?
Keywords: algorithm; Exponential-time algorithm; homomorphism
Exact colorings of graphs ★★
Author(s): Erickson
Keywords: graph coloring; ramsey theory
Dividing up the unrestricted partitions ★★
Begin with the generating function for unrestricted partitions:
(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...
Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.
Keywords: congruence properties; partition
The stubborn list partition problem ★★
Author(s): Cameron; Eschen; Hoang; Sritharan
Keywords: list partition; polynomial algorithm
Long rainbow arithmetic progressions ★★
Author(s): Fox; Jungic; Mahdian; Nesetril; Radoicic
For let denote the minimal number such that there is a rainbow in every equinumerous -coloring of for every
Keywords: arithmetic progression; rainbow
Reconstruction conjecture ★★★★
The deck of a graph is the multiset consisting of all unlabelled subgraphs obtained from by deleting a vertex in all possible ways (counted according to multiplicity).
Keywords: reconstruction
Finding k-edge-outerplanar graph embeddings ★★
Author(s): Bentz
Keywords: planar graph; polynomial algorithm
Approximation ratio for k-outerplanar graphs ★★
Author(s): Bentz
Keywords: approximation algorithms; planar graph; polynomial algorithm
Approximation Ratio for Maximum Edge Disjoint Paths problem ★★
Author(s): Bentz
Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm
Beneš Conjecture (graph-theoretic form) ★★★
Author(s): Beneš
Keywords:
Seymour's self-minor conjecture ★★★
Author(s): Seymour
Keywords: infinite graph; minor
Perfect 2-error-correcting codes over arbitrary finite alphabets. ★★
Author(s):
Keywords: 2-error-correcting; code; existence; perfect; perfect code
Are there an infinite number of lucky primes? ★
Author(s): Lazarus: Gardiner: Metropolis; Ulam
Something like Picard for 1-forms ★★
Author(s): Elsner
Keywords: Essential singularity; Holomorphic functions; Picard's theorem; Residue of 1-form; Riemann surfaces
The robustness of the tensor product ★★★
Author(s): Ben-Sasson; Sudan
The problem is to give a characterization of the pairs whose tensor product is robust.
Keywords: codes; coding; locally testable; robustness
Schanuel's Conjecture ★★★★
Author(s): Schanuel
Keywords: algebraic independence
Beneš Conjecture ★★★
Author(s): Beneš
Let be a non-empty finite set. Given a partition of , the stabilizer of , denoted , is the group formed by all permutations of preserving each block of .
Keywords:
Frankl's union-closed sets conjecture ★★
Author(s): Frankl
Keywords: