Главная

Rahul Jain

  1. A Game Theoretic Model for the Gaussian Broadcast Channel.

    Пт, 03/16/2012 - 15:01 — SomNambul
    Authors: Rahul Jain, Urbashi Mitra, Srinivas Yerramalli
    Subjects: Information Theory
    Abstract

    The 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.

  2. Strategic Arrivals into Queueing Networks: The Network Concert Queueing Game.

    Чт, 12/15/2011 - 15:01 — SomNambul
    Authors: Rahul Jain, Harsha Honnappa
    Subjects: Computer Science and Game Theory
    Abstract

    Queueing 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.

  3. Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards.

    Втр, 11/23/2010 - 16:02 — SomNambul
    Authors: Rahul Jain, Yi Gai, Bhaskar Krishnamachari
    Subjects: Optimization and Control
    Abstract

    In 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.

  4. The space complexity of recognizing well-parenthesized expressions.

    Втр, 04/20/2010 - 15:01 — SomNambul
    Authors: Rahul Jain, Ashwin Nayak
    Subjects: Computational Complexity
    Abstract

    We 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.

  5. Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity.

    Пт, 04/02/2010 - 15:02 — SomNambul
    Authors: Rahul Jain, Hartmut Klauck, Miklos Santha
    Subjects: Computational Complexity
    Abstract

    A 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.

  6. The Partition Bound for Classical Communication Complexity and Query Complexity.

    Пт, 10/23/2009 - 14:26 — SomNambul
    Authors: Rahul Jain, Hartmut Klauck
    Subjects: Computational Complexity
    Abstract

    We 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.

  7. Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas.

    Втр, 09/01/2009 - 12:47 — SomNambul
    Authors: Rahul Jain, Hartmut Klauck, Shengyu Zhang
    Subjects: Computational Complexity
    Abstract

    We 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.

Math-arch

RSS-материал