7 papers
Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT
Steven Heilman
Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of for every , where is th…
On the Convergence of Adam, Revisited
Steven Heilman, Sampad Mohanty
We show that projected Adam for online optimization with arbitrary moment decay parameters can have average regret bounded away from zero. A similar result of R…
An Upper Bound on Grothendieck's Constant
Steven Heilman
We show that Grothendieck's real constant can be upper bounded by projecting vectors onto a random plane through the origin and thresholding a degree five Hermite polynomial.…
Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools
Alina Du, Steven Heilman, Greta Panova
We give new examples of graphs and trees with dominating set sequences that are not log-concave. These examples were generated by PatternBoost, a transformer-based reinforcement le…
Independent Sets and Continued Fractions
Swee Hong Chan, Steven Heilman, Greta Panova
Linek's 1989 problem asks whether the numbers of independent sets of trees avoid infinitely many positive integers. We show that the set of natural numbers realized as the number o…
A Lower Bound for Grothendieck's Constant
Steven Heilman
We show that Grothendieck's real constant satisfies , improving on the lower bound of of Davie and Reeds from 1984 and 1991,…