activity
20142020
most citedA tighter bound on the number of relevant variables in a bounded degree Boolean function

4 citations · 11 across the 8 of their papers we have counts for

collaborators
Showing 2019Show all

2 papers · 1 filter

math.CO2019

Testing Gap k-planarity is NP-complete

John C. Urschel, Jake Wellens

For all , we show that deciding whether a graph is -planar is NP-complete, extending the well-known fact that deciding 1-planarity is NP-complete. Furthermore, we show…

cs.DM2019★ 4 cited

A tighter bound on the number of relevant variables in a bounded degree Boolean function

Jake Wellens

A classical theorem of Nisan and Szegedy says that a boolean function with degree as a real polynomial depends on at most of its variables. In recent work by Chiarel…