10 citations · 10 across the 3 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2017
Tree tribes and lower bounds for switching lemmas
Jenish C. Mehta
We show tight upper and lower bounds for switching lemmas obtained by the action of random -restrictions on boolean functions that can be expressed as decision trees in which ev…
cs.CC2016★ 10 cited
QCMA hardness of ground space connectivity for commuting Hamiltonians
David Gosset, Jenish C. Mehta, Thomas Vidick
In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (e…
cs.CC2013
Dynamic Complexity of Planar 3-connected Graph Isomorphism
Jenish C. Mehta
Dynamic Complexity (as introduced by Patnaik and Immerman) tries to express how hard it is to update the solution to a problem when the input is changed slightly. It considers the…