3 citations · 8 across the 7 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.CC2016
Did the Train Reach its Destination: The Complexity of Finding a Witness
Karthik C. S.
Recently, Dohrau et al. studied a zero-player game on switch graphs and proved that deciding the termination of the game is in NP coNP. In this short paper, we show that the…
cs.CG2016
On the Complexity of Closest Pair via Polar-Pair of Point-Sets
Roee David, Karthik C. S., Bundit Laekhanukit
Every graph can be represented by a collection of equi-radii spheres in a -dimensional metric such that there is an edge in if and only if the spheres correspon…
cs.CC2016
On the Sensitivity Conjecture for Disjunctive Normal Forms
Karthik C. S., Sébastien Tavenas
The sensitivity conjecture of Nisan and Szegedy [CC '94] asks whether for any Boolean function , the maximum sensitivity , is polynomially related to its block sensitivity…