Possible Research Problems

Approximation on Graphs

• Generalize the EPTAS on disk graphs to general geometric intersection graphs with a 'fatness' parameter.
• Generalize disk graphs to \((\alpha,\beta)\)-realizable disk graphs and check the hardness of approximating feedback set and approximating weighted vertex cover.

Approximating Matrix Permanent

• Determine the optimal approximation ratio for Hermitian PSD matrix permanent.
• Achieve better approximation for Hermitian PSD projector matrix permanent.
• Find a convex optimization version of the combinatorial algorithm described in here.

Karlin's Conjecture for Fictitious Play

• Karlin's conjecture seems to be ill-posed due to the tie-breaking issue. Can we generalize the tie-breaking protocol so that Karlin's conjecture holds? Check here.
• Prove Karlin's conjecture for a broader family of matrices than simply diagonal matrices.
• What is the correct convergence rate of fictitous play if we allow arbitrary tie-breaking?