91 citations · 766 across the 68 of their papers we have counts for
22 papers · 1 filter
A note on the partition bound for one-way classical communication complexity
Srinivasan Arunachalam, João F. Doriguello, Joao F. Doriguello +1
We present a linear program for a one-way version of the partition bound of Jain and Klauck, denoted , and show that it characterizes the one-way ran…
On relating one-way classical and quantum communication complexities
Naresh Goud Boddu, Rahul Jain, Han-Hsuan Lin
Communication complexity is the amount of communication needed to compute a function when the function inputs are distributed over multiple parties. In its simplest form, one-way c…
Reachability in High Treewidth Graphs
Rahul Jain, Raghunath Tewari
Reachability is the problem of deciding whether there is a path from one vertex to the other in the graph. Standard graph traversal algorithms such as DFS and BFS take linear time…
A Composition Theorem for Randomized Query Complexity
Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5
Let the randomized query complexity of a relation for error probability be denoted by . We prove that for any relation an…
Lifting randomized query complexity to randomized communication complexity
Anurag Anshu, Naresh B. Goud, Rahul Jain +2
We show that for a relation and a function (with ), $$\mathrm{R}_{1/3}(…
Extension Complexity of Independent Set Polytopes
Mika Göös, Rahul Jain, Thomas Watson
We exhibit an -node graph whose independent set polytope requires extended formulations of size exponential in . Previously, no explicit examples of -dimensional…