A curated list of unsolved problems in theoretical computer science.
Does envy-freeness up to any good (EFX) always exist for indivisible item allocation? An allocation is EFX if no agent envies another agent after removing any single item from the other agent's bun...
What is the best α for which α-MMS (maximin share) allocations always exist? The maximin share (MMS) is the value an agent can guarantee by dividing items into n bundles and receiving the worst bun...
What is the complexity of computing the ground state energy of the EPR Hamiltonian? The EPR Hamiltonian is a quantum Hamiltonian defined on a graph where each edge contains a projector onto the sym...
What is the best polynomial-time approximation ratio achievable for Max Di-Cut? Max Di-Cut is the directed graph version of Max Cut: given a directed graph, find a partition of vertices maximizing ...