Rahul Jain
A Game Theoretic Model for the Gaussian Broadcast Channel.
Fri, 03/16/2012 - 15:01 — SomNambulAuthors: Rahul Jain, Urbashi Mitra, Srinivas Yerramalli
Subjects: Information Theory
AbstractThe behavior of rational and selfish players (receivers) over a
multiple-input multiple-output Gaussian broadcast channel is investigated using
the framework of noncooperative game theory. In contrast to the game-theoretic
model of the Gaussian multiple access channel where the set of feasible actions
for each player is independent of other players' actions, the strategies of the
players in the broadcast channel are mutually coupled, usually by a sum power
or joint covariance constraint, and hence cannot be treated using traditional
Nash equilibrium solution concepts.Strategic Arrivals into Queueing Networks: The Network Concert Queueing Game.
Thu, 12/15/2011 - 15:01 — SomNambulAuthors: Rahul Jain, Harsha Honnappa
Subjects: Computer Science and Game Theory
AbstractQueueing networks are typically modelled assuming that the arrival process is
exogenous, and unaffected by admission control, scheduling policies, etc. In
many situations, however, users choose the time of their arrival strategically,
taking delay and other metrics into account. In this paper, we develop a
framework to study such strategic arrivals into queueing networks. We start by
deriving a functional strong law of large numbers (FSLLN) approximation to the
queueing network.Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards.
Tue, 11/23/2010 - 16:02 — SomNambulAuthors: Rahul Jain, Yi Gai, Bhaskar Krishnamachari
Subjects: Optimization and Control
AbstractIn the classic multi-armed bandits problem, the goal is to have a policy for
dynamically operating arms that each yield stochastic rewards with unknown
means. The key metric of interest is regret, defined as the gap between the
expected total reward accumulated by an omniscient player that knows the reward
means for each arm, and the expected total reward accumulated by the given
policy. The policies presented in prior work have storage, computation and
regret all growing linearly with the number of arms, which is not scalable when
the number of arms is large.The space complexity of recognizing well-parenthesized expressions.
Tue, 04/20/2010 - 15:01 — SomNambulAuthors: Rahul Jain, Ashwin Nayak
Subjects: Computational Complexity
AbstractWe show an Omega(sqrt{n}/T^3) lower bound for the space required by any
unidirectional constant-error randomized T-pass streaming algorithm that
recognizes whether an expression over two types of parenthesis is
well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak
(2009) and rigorously establishes the peculiar power of bi-directional streams
over unidirectional ones observed in the algorithms they present.Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity.
Fri, 04/02/2010 - 15:02 — SomNambulAuthors: Rahul Jain, Hartmut Klauck, Miklos Santha
Subjects: Computational Complexity
AbstractA Direct Sum Theorem holds in a model of computation, when solving some k
input instances together is k times as expensive as solving one. We show that
Direct Sum Theorems hold in the models of deterministic and randomized decision
trees for all relations. We also note that a near optimal Direct Sum Theorem
holds for quantum decision trees for boolean functions.The Partition Bound for Classical Communication Complexity and Query Complexity.
Fri, 10/23/2009 - 14:26 — SomNambulAuthors: Rahul Jain, Hartmut Klauck
Subjects: Computational Complexity
AbstractWe describe new lower bounds for randomized communication complexity and
query complexity which we call the partition bounds. They are expressed as the
optimum value of linear programs. For communication complexity we show that the
partition bound is stronger than both the rectangle/corruption bound and the
\gamma_2/generalized discrepancy bounds. In the model of query complexity we
show that the partition bound is stronger than the approximate polynomial
degree and classical adversary bounds.Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas.
Tue, 09/01/2009 - 12:47 — SomNambulAuthors: Rahul Jain, Hartmut Klauck, Shengyu Zhang
Subjects: Computational Complexity
AbstractWe show lower bounds of $\Omega(\sqrt{n})$ and $\Omega(n^{1/4})$ on the
randomized and quantum communication complexity, respectively, of all
$n$-variable read-once Boolean formulas. Our results complement the recent
lower bound of $\Omega(n/8^d)$ by Leonardos and Saks and
$\Omega(n/2^{\Omega(d\log d)})$ by Jayram, Kopparty and Raghavendra for
randomized communication complexity of read-once Boolean formulas with depth
$d$. We obtain our result by "embedding" either the Disjointness problem or its
complement in any given read-once Boolean formula.
User login
