21 citations · 61 across the 21 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.CC2018★ 1 cited
Sum of squares bounds for the ordering principle
Aaron Potechin
In this paper, we analyze the sum of squares hierarchy (SOS) on the ordering principle on elements. We prove that degree SOS can prove the ordering principl…
cs.CC2018
On the Approximation Resistance of Balanced Linear Threshold Functions
Aaron Potechin
In this paper, we show that there exists a balanced linear threshold function (LTF) which is unique games hard to approximate, refuting a conjecture of Austrin, Benabbas, and Magen…
cs.FL2018
Lengths of Words Accepted by Nondeterministic Finite Automata
Aaron Potechin, Jeffrey Shallit
We consider two natural problems about nondeterministic finite automata. First, given such an automaton M of n states, and a length l, does M accept a word of length l? We show tha…