BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Rahul Jain

Rahul Jain appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational Complexityquant-phmath.OCInformation Theorymath.ITMachine LearningSystems and ControlComputer Science and Game Theorymath.PRArtificial IntelligenceData Structures and Algorithmseess.SYComputer VisionDiscrete MathematicsDistributed, Parallel, and Cluster Computingecon.THLogic in Computer Sciencemath.CONetworking and Internet Architecturenucl-exPerformancephysics.ins-det

Catalog footprint

What is connected

56works
22topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

56 published item(s)

preprint2026arXiv

MechVerse: Evaluating Physical Motion Consistency in Video Generation Models

Text- and image-conditioned video generation models have achieved strong visual fidelity and temporal coherence, but they often fail to generate motion governed by kinematic and geometric constraints. In these settings, object parts must remain rigid, maintain contact or coupling with neighboring components, and transfer motion consistently across connected parts. These requirements are especially explicit in articulated mechanical assemblies, where motion is constrained by rigid-link geometry, contact/coupling relations, and transmission through kinematic chains. A generated video may therefore appear plausible while violating the intended mechanism, such as rotating a part that should translate, deforming a rigid component, breaking coupling between parts, or failing to move downstream components. To evaluate this gap, We introduce MechVerse, a benchmark for mechanically consistent image-to-video generation. MechVerse contains 21,156 synthetic clips from 1,357 mechanical assemblies across 141 categories, organized into three tiers of increasing kinematic complexity: independent articulation, pairwise coupling, and densely coupled multi-part mechanisms. Each clip is paired with a structured prompt describing part identities, stationary supports, moving components, motion primitives, direction, speed/extent, and inter-part dependencies. We evaluate proprietary, open-source, and fine-tuned image-to-video models using standard video metrics, instruction-following scores, and human judgments of motion correctness and kinematic coupling. Results show that current models can preserve appearance and smoothness while failing to generate mechanically admissible motion, with errors increasing as coupling complexity grows. MechVerse provides a benchmark for measuring and improving mechanism-aware video generation from image and language inputs.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Robust LLM Alignment via Distributionally Robust Direct Preference Optimization

A major challenge in aligning large language models (LLMs) with human preferences is the issue of distribution shift. LLM alignment algorithms rely on static preference datasets, assuming that they accurately represent real-world user preferences. However, user preferences vary significantly across geographical regions, demographics, linguistic patterns, and evolving cultural trends. This preference distribution shift leads to catastrophic alignment failures in many real-world applications. We address this problem using the principled framework of distributionally robust optimization, and develop two novel distributionally robust direct preference optimization (DPO) algorithms, namely, Wasserstein DPO (WDPO) and Kullback-Leibler DPO (KLDPO). We characterize the sample complexity of learning the optimal policy parameters for WDPO and KLDPO. Moreover, we propose scalable gradient descent-style learning algorithms by developing suitable approximations for the challenging minimax loss functions of WDPO and KLDPO. Our empirical experiments using benchmark data sets and LLMs demonstrate the superior performance of WDPO and KLDPO in substantially improving the alignment when there is a preference distribution shift.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

When Dynamics Shift, Robust Task Inference Wins: Offline Imitation Learning with Behavior Foundation Models Revisited

Behavior Foundation Models (BFMs) enable scalable imitation learning (IL) by pretraining task-agnostic representations that can be rapidly adapted to new tasks. However, existing BFMs assume fixed environment dynamics, limiting their robustness under real-world shifts such as changes in friction, actuation, or sensor noise. We address this by formulating BFM task-inference as a robust minimax optimization problem, enabling adaptation to worst-case dynamics perturbations without modifying pretraining. To the best of our knowledge, this is the first BFM-based framework that achieves robustness to dynamics shifts while relying solely on offline data from a single nominal environment. Our approach significantly outperforms standard BFM and robust offline IL baselines under dynamics shifts. These results demonstrate that robust policy can be achieved entirely at task-inference time, improving the practicality of BFMs in dynamic settings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints

We study regret minimization for infinite-horizon average-reward Markov Decision Processes (MDPs) under cost constraints. We start by designing a policy optimization algorithm with carefully designed action-value estimator and bonus term, and show that for ergodic MDPs, our algorithm ensures $\widetilde{O}(\sqrt{T})$ regret and constant constraint violation, where $T$ is the total number of time steps. This strictly improves over the algorithm of (Singh et al., 2020), whose regret and constraint violation are both $\widetilde{O}(T^{2/3})$. Next, we consider the most general class of weakly communicating MDPs. Through a finite-horizon approximation, we develop another algorithm with $\widetilde{O}(T^{2/3})$ regret and constraint violation, which can be further improved to $\widetilde{O}(\sqrt{T})$ via a simple modification, albeit making the algorithm computationally inefficient. As far as we know, these are the first set of provable algorithms for weakly communicating MDPs with cost constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Online Bayesian Optimization for Beam Alignment in the SECAR Recoil Mass Separator

The SEparator for CApture Reactions (SECAR) is a next-generation recoil separator system at the Facility for Rare Isotope Beams (FRIB) designed for the direct measurement of capture reactions on unstable nuclei in inverse kinematics. To maximize the performance of the device, careful beam alignment to the central ion optical axis needs to be achieved. This can be difficult to attain through manual tuning by human operators without potentially leaving the system in a sub-optimal and irreproducible state. In this work, we present the first development of online Bayesian optimization with a Gaussian process model to tune an ion beam through a nuclear astrophysics recoil separator. We show that the method achieves small incoming angular deviations (0-1 mrad) in an efficient and reproducible manner that is at least 3 times faster than standard hand-tuning. This method is now routinely used for all separator tuning.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Communication and Control Strategies for a Multi-Agent System in the Presence of an Adversary

We consider a multi-agent system in which a decentralized team of agents controls a stochastic system in the presence of an adversary. Instead of committing to a fixed information sharing protocol, the agents can strategically decide at each time whether to share their private information with each other or not. The agents incur a cost whenever they communicate with each other and the adversary may eavesdrop on their communication. Thus, the agents in the team must effectively coordinate with each other while being robust to the adversary's malicious actions. We model this interaction between the team and the adversary as a stochastic zero-sum game where the team aims to minimize a cost while the adversary aims to maximize it. Under some assumptions on the adversary's capabilities, we characterize a min-max control and communication strategy for the team. We supplement this characterization with several structural results that can make the computation of the min-max strategy more tractable.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Control of Partially Observable Markov Decision Processes with Finite Linear Temporal Logic Constraints

Autonomous agents often operate in scenarios where the state is partially observed. In addition to maximizing their cumulative reward, agents must execute complex tasks with rich temporal and logical structures. These tasks can be expressed using temporal logic languages like finite linear temporal logic (LTL_f). This paper, for the first time, provides a structured framework for designing agent policies that maximize the reward while ensuring that the probability of satisfying the temporal logic specification is sufficiently high. We reformulate the problem as a constrained partially observable Markov decision process (POMDP) and provide a novel approach that can leverage off-the-shelf unconstrained POMDP solvers for solving it. Our approach guarantees approximate optimality and constraint satisfaction with high probability. We demonstrate its effectiveness by implementing it on several models of interest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Direct Product Theorem for One-Way Quantum Communication

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, ζ> 0$ and any $k\geq1$, we show that \[ \mathrm{Q}^1_{1-(1-\varepsilon)^{Ω(ζ^6k/\log|\mathcal{Z}|)}}(f^k) = Ω\left(k\left(ζ^5\cdot\mathrm{Q}^1_{\varepsilon + 12ζ}(f) - \log\log(1/ζ)\right)\right),\] where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $\varepsilon$ and $f^k$ denotes $k$ parallel instances of $f$. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszlényi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G = (q, \mathcal{X}\times\mathcal{Y}, \mathcal{A}\times\mathcal{B}, \mathsf{V})$ where $q$ is a distribution on $\mathcal{X}\times\mathcal{Y}$ anchored on any one side with anchoring probability $ζ$, then \[ ω^*(G^k) = \left(1 - (1-ω^*(G))^5\right)^{Ω\left(\frac{ζ^2 k}{\log(|\mathcal{A}|\cdot|\mathcal{B}|)}\right)}\] where $ω^*(G)$ represents the entangled value of the game $G$. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A near-optimal direct-sum theorem for communication complexity

We show a near optimal direct-sum theorem for the two-party randomized communication complexity. Let $f\subseteq X \times Y\times Z$ be a relation, $\varepsilon> 0$ and $k$ be an integer. We show, $$\mathrm{R}^{\mathrm{pub}}_\varepsilon(f^k) \cdot \log(\mathrm{R}^{\mathrm{pub}}_\varepsilon(f^k)) \ge Ω(k \cdot \mathrm{R}^{\mathrm{pub}}_\varepsilon(f)) \enspace,$$ where $f^k= f \times \ldots \times f$ ($k$-times) and $\mathrm{R}^{\mathrm{pub}}_\varepsilon(\cdot)$ represents the public-coin randomized communication complexity with worst-case error $\varepsilon$. Given a protocol $\mathcal{P}$ for $f^k$ with communication cost $c \cdot k$ and worst-case error $\varepsilon$, we exhibit a protocol $\mathcal{Q}$ for $f$ with external-information-cost $O(c)$ and worst-error $\varepsilon$. We then use a message compression protocol due to Barak, Braverman, Chen and Rao [2013] for simulating $\mathcal{Q}$ with communication $O(c \cdot \log(c\cdot k))$ to arrive at our result. To show this reduction we show some new chain-rules for capacity, the maximum information that can be transmitted by a communication channel. We use the powerful concept of Nash-Equilibrium in game-theory, and its existence in suitably defined games, to arrive at the chain-rules for capacity. These chain-rules are of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Risk Aware Two-Stage Market Mechanism for Electricity with Renewable Generation

Over the last few decades, electricity markets around the world have adopted multi-settlement structures, allowing for balancing of supply and demand as more accurate forecast information becomes available. Given increasing uncertainty due to adoption of renewables, more recent market design work has focused on optimization of expectation of some quantity, e.g. social welfare. However, social planners and policy makers are often risk averse, so that such risk neutral formulations do not adequately reflect prevailing attitudes towards risk, nor explain the decisions that follow. Hence we incorporate the commonly used risk measure conditional value at risk (CVaR) into the central planning objective, and study how a two-stage market operates when the individual generators are risk neutral. Our primary result is to show existence (by construction) of a sequential competitive equilibrium (SCEq) in this risk-aware two-stage market. Given equilibrium prices, we design a market mechanism which achieves social cost minimization assuming that agents are non strategic.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes

Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-reward Markov Decision Processes (MDPs). The first algorithm reduces the problem to the discounted-reward version and achieves $\mathcal{O}(T^{2/3})$ regret after $T$ steps, under the minimal assumption of weakly communicating MDPs. To our knowledge, this is the first model-free algorithm for general MDPs in this setting. The second algorithm makes use of recent advances in adaptive algorithms for adversarial multi-armed bandits and improves the regret to $\mathcal{O}(\sqrt{T})$, albeit with a stronger ergodic assumption. This result significantly improves over the $\mathcal{O}(T^{3/4})$ regret achieved by the only existing model-free algorithm by Abbasi-Yadkori et al. (2019a) for ergodic MDPs in the infinite-horizon average-reward setting.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multiple Source Replacement Path Problem

One of the classical line of work in graph algorithms has been the Replacement Path Problem: given a graph $G$, $s$ and $t$, find shortest paths from $s$ to $t$ avoiding each edge $e$ on the shortest path from $s$ to $t$. These paths are called replacement paths in literature. For an undirected and unweighted graph, (Malik, Mittal, and Gupta, Operation Research Letters, 1989) and (Hershberger and Suri, FOCS 2001) designed an algorithm that solves the replacement path problem in $\tilde O(m+n)$ time. It is natural to ask whether we can generalize the replacement path problem: {\em can we find all replacement paths from a source $s$ to all vertices in $G$?} This problem is called the Single Source Replacement Path Problem. Recently (Chechik and Cohen, SODA 2019) designed a randomized combinatorial algorithm that solves the Single Source Replacement Path Problem in $\tilde O(m\sqrt n\ + n^2)$ time. One of the questions left unanswered by their work is the case when there are many sources, not one. When there are $n$ sources, the combinatorial algorithm of (Bernstein and Karger, STOC 2009) can be used to find all pair replacement path in $\tilde O(mn + n^3)$ time. However, there is no result known for any general $σ$. Thus, the problem we study is defined as follows: given a set of $σ$ sources, we want to find the replacement path from these sources to all vertices in $G$. We give a randomized combinatorial algorithm for this problem that takes $\tilde O(m\sqrt{n σ} +\ σn^2)$ time. This result generalizes both results known for this problem. Our algorithm is much different and arguably simpler than (Chechik and Cohen, SODA 2019). Like them, we show a matching conditional lower bound using the Boolean Matrix Multiplication conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Non-indexability of the Stochastic Appointment Scheduling Problem

Consider a set of jobs with independent random service times to be scheduled on a single machine. The jobs can be surgeries in an operating room, patients' appointments in outpatient clinics, etc. The challenge is to determine the optimal sequence and appointment times of jobs to minimize some function of the server idle time and service start-time delay. We introduce a generalized objective function of delay and idle time, and consider $l_1$-type and $l_2$-type cost functions as special cases of interest. Determining an index-based policy for the optimal sequence in which to schedule jobs has been an open problem for many years. For example, it was conjectured that `least variance first' (LVF) policy is optimal for the $l_1$-type objective. This is known to be true for the case of two jobs with specific distributions. A key result in this paper is that the optimal sequencing problem is non-indexable, i.e., neither the variance, nor any other such index can be used to determine the optimal sequence in which to schedule jobs for $l_1$ and $l_2$-type objectives. We then show that given a sequence in which to schedule the jobs, sample average approximation yields a solution which is statistically consistent.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Time Space Optimal Algorithm for Computing Separators in Bounded Genus Graphs

A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an important computational task. In this paper, we present a polynomial time algorithm that uses $O(g^{1/2}n^{1/2}\log n)$-space to find an $O(g^{1/2}n^{1/2})$-sized separator of a graph having $n$ vertices and embedded on a surface of genus $g$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

A minimax approach to one-shot entropy inequalities

One-shot information theory entertains a plethora of entropic quantities, such as the smooth max-divergence, hypothesis testing divergence and information spectrum divergence, that characterize various operational tasks and are used to prove the asymptotic behavior of various tasks in quantum information theory. Tight inequalities between these quantities are thus of immediate interest. In this note we use a minimax approach (appearing previously for example in the proofs of the quantum substate theorem), to simplify the quantum problem to a commutative one, which allows us to derive such inequalities. Our derivations are conceptually different from previous arguments and in some cases lead to tighter relations. We hope that the approach discussed here can lead to progress in open problems in quantum Shannon theory, and exemplify this by applying it to a simple case of the joint smoothing problem.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Efficient methods for one-shot quantum communication

We address the question of efficient implementation of quantum protocols, with small communication and entanglement, and short depth circuit for encoding or decoding. We introduce two new methods to achieve this, the first method involving two new versions of convex-split lemma that use small amount of additional resource (in comparison to prior version) and the second method being inspired by the technique of classical correlated sampling in computer science. These lead to a series of new consequences, as follows. First, we consider the task of quantum decoupling, where the aim is to apply an operation on a n-qubit register so as to make it independent of an inaccessible quantum system. Many previous works achieve decoupling with the aid of a random unitary. It is known that random unitaries can be replaced by random circuits of size O(n\log n) and depth poly(\log n), or unitary 2-designs based on Clifford circuits of similar size and depth. We show that given any choice of basis such as the computational basis, decoupling can be achieved by a unitary that takes basis vectors to basis vectors. Thus, the circuit acts in a `classical' manner and additionally uses O(n) catalytic qubits in maximally mixed quantum state. Our unitary performs addition and multiplication modulo a prime and hence achieves a circuit size of O(n\log n) and logarithmic depth. This shows that the circuit complexity of integer multiplication (modulo a prime) is lower bounded by the optimal circuit complexity of decoupling. Next, we construct a new one-shot entanglement-assisted protocol for quantum channel coding that achieves near-optimal communication through a given channel. The number of qubits of pre-shared entanglement is exponentially smaller than that in the previous protocol near-optimal in communication. We also achieve similar results for one-shot quantum state redistribution.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Parallel Device-Independent Quantum Key Distribution

A prominent application of quantum cryptography is the distribution of cryptographic keys that are provably secure. Recently, such security proofs were extended by Vazirani and Vidick (Physical Review Letters, 113, 140501, 2014) to the device-independent (DI) scenario, where the users do not need to trust the integrity of the underlying quantum devices. The protocols analyzed by them and by subsequent authors all require a sequential execution of N multiplayer games, where N is the security parameter. In this work, we prove unconditional security of a protocol where all games are executed in parallel. Besides decreasing the number of time-steps necessary for key generation, this result reduces the security requirements for DI-QKD by allowing arbitrary information leakage of each user's inputs within his or her lab. To the best of our knowledge, this is the first parallel security proof for a fully device-independent QKD protocol. Our protocol tolerates a constant level of device imprecision and achieves a linear key rate.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Partially smoothed information measures

Smooth entropies are a tool for quantifying resource trade-offs in (quantum) information theory and cryptography. In typical bi- and multi-partite problems, however, some of the sub-systems are often left unchanged and this is not reflected by the standard smoothing of information measures over a ball of close states. We propose to smooth instead only over a ball of close states which also have some of the reduced states on the relevant sub-systems fixed. This partial smoothing of information measures naturally allows to give more refined characterizations of various information-theoretic problems in the one-shot setting. In particular, we immediately get asymptotic second-order characterizations for tasks such as privacy amplification against classical side information or classical state splitting. For quantum problems like state merging the general resource trade-off is tightly characterized by partially smoothed information measures as well.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approachability in Stackelberg Stochastic Games with Vector Costs

The notion of approachability was introduced by Blackwell [1] in the context of vector-valued repeated games. The famous Blackwell's approachability theorem prescribes a strategy for approachability, i.e., for `steering' the average cost of a given agent towards a given target set, irrespective of the strategies of the other agents. In this paper, motivated by the multi-objective optimization/decision making problems in dynamically changing environments, we address the approachability problem in Stackelberg stochastic games with vector valued cost functions. We make two main contributions. Firstly, we give a simple and computationally tractable strategy for approachability for Stackelberg stochastic games along the lines of Blackwell's. Secondly, we give a reinforcement learning algorithm for learning the approachable strategy when the transition kernel is unknown. We also recover as a by-product Blackwell's necessary and sufficient condition for approachability for convex sets in this set up and thus a complete characterization. We also give sufficient conditions for non-convex sets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Asynchronous Optimization Over Heterogeneous Networks via Consensus ADMM

This paper considers the distributed optimization of a sum of locally observable, non-convex functions. The optimization is performed over a multi-agent networked system, and each local function depends only on a subset of the variables. An asynchronous and distributed alternating directions method of multipliers (ADMM) method that allows the nodes to defer or skip the computation and transmission of updates is proposed in the paper. The proposed algorithm utilizes different approximations in the update step, resulting in proximal and majorized ADMM variants. Both variants are shown to converge to a local minimum, under certain regularity conditions. The proposed asynchronous algorithms are also applied to the problem of cooperative localization in wireless ad hoc networks, where it is shown to outperform the other state-of-the-art localization algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Extension Complexity of Independent Set Polytopes

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $Ω(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $Θ(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit depth.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Matching Multiplications in Bit-Vector Formulas

Bit-vector formulas arising from hardware verification problems often contain word-level arithmetic operations. Empirical evidence shows that state-of-the-art SMT solvers are not very efficient at reasoning about bit-vector formulas with multiplication. This is particularly true when multiplication operators are decomposed and represented in alternative ways in the formula.We present a pre-processing heuristic that identifies certain types of decomposed multipliers, and adds special assertions to the input formula encoding the equivalence of sub-terms to word-level multiplication. The pre-processed formulas are then solved using an SMT solver. Our experiments with three SMT solvers show that our heuristic allows several formulas to be solved quickly, while the same formulas time out without the pre-processing step.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits

We consider the problem of learning in single-player and multiplayer multiarmed bandit models. Bandit problems are classes of online learning problems that capture exploration versus exploitation tradeoffs. In a multiarmed bandit model, players can pick among many arms, and each play of an arm generates an i.i.d. reward from an unknown distribution. The objective is to design a policy that maximizes the expected reward over a time horizon for a single player setting and the sum of expected rewards for the multiplayer setting. In the multiplayer setting, arms may give different rewards to different players. There is no separate channel for coordination among the players. Any attempt at communication is costly and adds to regret. We propose two decentralizable policies, $\tt E^3$ ($\tt E$-$\tt cubed$) and $\tt E^3$-$\tt TS$, that can be used in both single player and multiplayer settings. These policies are shown to yield expected regret that grows at most as O($\log^{1+ε} T$). It is well known that $\log T$ is the lower bound on the rate of growth of regret even in a centralized case. The proposed algorithms improve on prior work where regret grew at O($\log^2 T$). More fundamentally, these policies address the question of additional cost incurred in decentralized online learning, suggesting that there is at most an $ε$-factor cost in terms of order of regret. This solves a problem of relevance in many domains and had been open for a while.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Decentralized Control with Asymmetric One-Step Delayed Information Sharing

We consider optimal control of decentralized LQG problems for plants controlled by two players having asymmetric information sharing patterns between them. In one scenario, players are assumed to have a bidirectional error-free, unlimited rate communication channel with no delay in one direction and a unit delay in the other. In another scenario, the communication channel is assumed to be unidirectional with a unit delay. Delayed information sharing patterns in general do not admit linear optimal control laws and are thus difficult to control optimally. However, in these scenarios, we show that the problem has a partially nested information structure, and thus linear optimal control laws exist. Summary statistics to characterize these laws are developed and deterministic convex optimization problems are formulated whose solutions yield the optimal control laws. The state feedback case is solved for both scenarios and extended to output and partial output feedback in case of bidirectional and unidirectional channels respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Partition bound is quadratically tight for product distributions

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $μ$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $$\mathsf{CC}^μ_{0.49}(f) = O\left(\left(\log \mathsf{prt}_{1/8}(f) \cdot \log \log \mathsf{prt}_{1/8}(f)\right)^2\right),$$ where $\mathsf{CC}^μ_\varepsilon(f)$ is the distributional communication complexity of $f$ with error at most $\varepsilon$ under the distribution $μ$ and $\mathsf{prt}_{1/8}(f)$ is the {\em partition bound} of $f$, as defined by Jain and Klauck [{\em Proc. 25th CCC}, 2010]. We also prove a similar bound in terms of $\mathsf{IC}_{1/8}(f)$, the {\em information complexity} of $f$, namely, $$\mathsf{CC}^μ_{0.49}(f) = O\left(\left(\mathsf{IC}_{1/8}(f) \cdot \log \mathsf{IC}_{1/8}(f)\right)^2\right).$$ The latter bound was recently and independently established by Kol [{\em Proc. 48th STOC}, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let $g : \{0,1\}^n \rightarrow \{0,1\}$ be a function. For every bit-wise product distribution $μ$ on $\{0,1\}^n$, we show that $$\mathsf{QC}^μ_{0.49}(g) = O\left(\left( \log \mathsf{qprt}_{1/8}(g) \cdot \log \log\mathsf{qprt}_{1/8}(g) \right)^2 \right),$$ where $\mathsf{QC}^μ_{\varepsilon}(g)$ is the distributional query complexity of $f$ with error at most $\varepsilon$ under the distribution $μ$ and $\mathsf{qprt}_{1/8}(g))$ is the {\em query partition bound} of the function $g$. Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for {\em product} distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Communication tasks with infinite quantum-classical separation

Quantum resources can be more powerful than classical resources - a quantum computer can solve certain problems exponentially faster than a classical computer, and computing a function of two people's inputs can be done with exponentially less communication with quantum messages than with classical ones. Here we consider a task between two players, Alice and Bob where quantum resources are infinitely more powerful than classical ones. Alice is given a string of length n, and Bob's task is to exclude certain combinations of bits that Alice might have. If Alice must send classical messages, then she must reveal nearly n bits of information to Bob, but if she is allowed to send quantum bits, the amount of information she must reveal goes to zero with increasing n. Next, we consider a version of the task where the parties can only send classical messages but may have access to entanglement. When assisted by entanglement, Alice only needs to send a constant number of bits, while without entanglement, the number of bits Alice must send grows linearly with n. The task is related to the PBR theorem which arises in the context of the foundations of quantum theory.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A parallel repetition theorem for entangled two-player one-round games under product distributions

We show a parallel repetition theorem for the entangled value $ω^*(G)$ of any two-player one-round game $G$ where the questions $(x,y) \in \mathcal{X}\times\mathcal{Y}$ to Alice and Bob are drawn from a product distribution on $\mathcal{X}\times\mathcal{Y}$. We show that for the $k$-fold product $G^k$ of the game $G$ (which represents the game $G$ played in parallel $k$ times independently), $ ω^*(G^k) =\left(1-(1-ω^*(G))^3\right)^{Ω\left(\frac{k}{\log(|\mathcal{A}| \cdot |\mathcal{B}|)}\right)} $, where $\mathcal{A}$ and $\mathcal{B}$ represent the sets from which the answers of Alice and Bob are drawn.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A quadratically tight partition bound for classical communication complexity and query complexity

In this work we introduce, both for classical communication complexity and query complexity, a modification of the 'partition bound' introduced by Jain and Klauck [2010]. We call it the 'public-coin partition bound'. We show that (the logarithm to the base two of) its communication complexity and query complexity versions form, for all relations, a quadratically tight lower bound on the public-coin randomized communication complexity and randomized query complexity respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A queueing model with independent arrivals, and its fluid and diffusion limits

We introduce the Δ(i)/GI/1 queue, a new queueing model. In this model, customers from a given population independently sample a time to arrive from some given distribution F. Thus, the arrival times are an ordered statistics, and the inter-arrival times are differences of consecutive ordered statistics. They are served by a single server which provides service according to a general distribution G, with independent service times. The exact model is analytically intractable. Thus, we develop fluid and diffusion limits for the various stochastic processes, and performance metrics. The fluid limit of the queue length is observed to be a reflected process, while the diffusion limit is observed to be a function of a Brownian motion and a Brownian bridge process, and is given by a 'netput' process and a directional derivative of the Skorokhod reflected fluid netput in the direction of a diffusion refinement of the netput process. We also observe what may be interpreted as a transient Little's law. Sample path analysis reveals various operating regimes where the diffusion limit switches between a free diffusion, a reflected diffusion process and the zero process, with possible discontinuities during regime switches. The weak convergence is established in the M1 topology, and it is also shown that this is not possible in the J1 topology.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A strong direct product theorem for the tribes function via the smooth-rectangle bound

The main result of this paper is an optimal strong direct product result for the two-party public-coin randomized communication complexity of the Tribes function. This is proved by providing an alternate proof of the optimal lower bound of Ω(n) for the randomised communication complexity of the Tribes function using the so-called smooth-rectangle bound, introduced by Jain and Klauck [JK10]. The optimal Ω(n) lower bound for Tribes was originally proved by Jayram, Kumar and Sivakumar [JKS03], using a more powerful lower bound technique, namely the information complexity bound. The information complexity bound is known to be at least as strong a lower bound method as the smooth-rectangle bound [KLL+12]. On the other hand, we are not aware of any function or relation for which the smooth-rectangle bound is (asymptotically) smaller than its public-coin randomized communication complexity. The optimal direct product for Tribes is obtained by combining our smooth-rectangle bound for tribes with the strong direct product result of Jain and Yao [JY12] in terms of smooth-rectangle bound.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Conclusive Exclusion of Quantum States

In the task of quantum state exclusion we consider a quantum system, prepared in a state chosen from a known set. The aim is to perform a measurement on the system which can conclusively rule that a subset of the possible preparation procedures can not have taken place. We ask what conditions the set of states must obey in order for this to be possible and how well we can complete the task when it is not. The task of quantum state discrimination forms a subclass of this set of problems. Within this paper we formulate the general problem as a Semidefinite Program (SDP), enabling us to derive sufficient and necessary conditions for a measurement to be optimal. Furthermore, we obtain a necessary condition on the set of states for exclusion to be achievable with certainty and give a construction for a lower bound on the probability of error. This task of conclusively excluding states has gained importance in the context of the foundations of quantum mechanics due to a result of Pusey, Barrett and Rudolph (PBR). Motivated by this, we use our SDP to derive a bound on how well a class of hidden variable models can perform at a particular task, proving an analogue of Tsirelson's bound for the PBR experiment and the optimality of a measurement given by PBR in the process. We also introduce variations of conclusive exclusion, including unambiguous state exclusion, and state exclusion with worst case error.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multipartite Quantum Correlation and Communication Complexities

The concepts of quantum correlation complexity and quantum communication complexity were recently proposed to quantify the minimum amount of resources needed in generating bipartite classical or quantum states in the single-shot setting. The former is the minimum size of the initially shared state $σ$ on which local operations by the two parties (without communication) can generate the target state $ρ$, and the latter is the minimum amount of communication needed when initially sharing nothing. In this paper, we generalize these two concepts to multipartite cases, for both exact and approximate state generation. Our results are summarized as follows. (1) For multipartite pure states, the correlation complexity can be completely characterized by local ranks of sybsystems. (2) We extend the notion of PSD-rank of matrices to that of tensors, and use it to bound the quantum correlation complexity for generating multipartite classical distributions. (3) For generating multipartite mixed quantum states, communication complexity is not always equal to correlation complexity (as opposed to bipartite case). But they differ by at most a factor of 2. Generating a multipartite mixed quantum state has the same communication complexity as generating its optimal purification. But for correlation complexity of these two tasks can be different (though still related by less than a factor of 2). (4) To generate a bipartite classical distribution $P(x,y)$ approximately, the quantum communication complexity is completely characterized by the approximate PSD-rank of $P$. The quantum correlation complexity of approximately generating multipartite pure states is bounded by approximate local ranks.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Transitory Queueing

We introduce a framework and develop a theory of transitory queueing models. These are models that are not only non-stationary and time-varying but also have other features such as the queueing system operates over finite time, or only a finite population arrives. Such models are relevant in many real-world settings, from queues at post-offces, DMV, concert halls and stadia to out-patient departments at hospitals. We develop fluid and diffusion limits for a large class of transitory queueing models. We then introduce three specific models that fit within this framework, namely, the Delta(i)/GI/1 model, the conditioned G/GI/1 model, and an arrival model of scheduled traffic with epoch uncertainty. We show that asymptotically these models are distributionally equivalent, i.e., they have the same fluid and diffusion limits. We note that our framework provides the first ever way of analyzing the standard G/GI/1 model when we condition on the number of arrivals. In obtaining these results, we provide generalizations and extensions of the Glivenko-Cantelli and Donskers Theorem for empirical processes with triangular arrays. Our analysis uses the population acceleration technique that we introduce and develop. This may be useful in analysis of other non-stationary and non-ergodic queuing models.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The space complexity of recognizing well-parenthesized expressions in the streaming model: the Index function revisited

We show an Omega(sqrt{n}/T) 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 that bidirectional streams are exponentially more efficient in space usage as compared with unidirectional ones. We obtain the lower bound by establishing the minimum amount of information that is necessarily revealed by the players about their respective inputs in a two-party communication protocol for a variant of the Index function, namely Augmented Index. The information cost trade-off is obtained by a novel application of the conceptually simple and familiar ideas such as average encoding and the cut-and-paste property of randomized protocols. Motivated by recent examples of exponential savings in space by streaming quantum algorithms, we also study quantum protocols for Augmented Index. Defining an appropriate notion of information cost for quantum protocols involves a delicate balancing act between its applicability and the ease with which we can analyze it. We define a notion of quantum information cost which reflects some of the non-intuitive properties of quantum information and give a trade-off for this notion. While this trade-off demonstrates the strength of our proof techniques, it does not lead to a space lower bound for checking parentheses. We leave such an implication for quantum streaming algorithms as an intriguing open question.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Unidirectional Input/Output Streaming Complexity of Reversal and Sorting

We consider unidirectional data streams with restricted access, such as read-only and write-only streams. For read-write streams, we also introduce a new complexity measure called expansion, the ratio between the space used on the stream and the input size. We give tight bounds for the complexity of reversing a stream of length $n$ in several of the possible models. In the read-only and write-only model, we show that $p$-pass algorithms need memory space $Θ(n/p)$. But if either the output stream or the input stream is read-write, then the complexity falls to $Θ(n/p^2)$. It becomes $polylog(n)$ if $p = O(log n)$ and both streams are read-write. We also study the complexity of sorting a stream and give two algorithms with small expansion. Our main sorting algorithm is randomized and has $O(1)$ expansion, $O(log n)$ passes and $O(log n)$ memory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Nash Equilibrium Need Not Exist in the Locational Marginal Pricing Mechanism

Locational marginal pricing (LMP) is a widely employed method for pricing electricity in the wholesale electricity market. Although it is well known that the LMP mechanism is vulnerable to market manipulation, there is little literature providing a systematic analysis of this phenomenon. In the first part of this paper, we investigate the economic dispatch outcomes of the LMP mechanism with strategic agents. We show via counterexamples, that contrary to popular belief, a Nash equilibrium may not exist. And when it exists, the price of anarchy may be arbitrarily large. We then provide two sufficient conditions under either of which an efficient Nash equilibria exists. Last, we propose a new market mechanism for electricity markets, the Power Network Second Price (PNSP) mechanism that always induces an efficient Nash equilibrium. We briefly address the extensions on the demand side.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A strong direct product theorem in terms of the smooth rectangle bound

A strong direct product theorem states that, in order to solve k instances of a problem, if we provide less than k times the resource required to compute one instance, then the probability of overall success is exponentially small in k. In this paper, we consider the model of two-way public-coin communication complexity and show a strong direct product theorem for all relations in terms of the smooth rectangle bound, introduced by Jain and Klauck as a generic lower bound method in this model. Our result therefore uniformly implies a strong direct product theorem for all relations for which an (asymptotically) optimal lower bound can be provided using the smooth rectangle bound, for example Inner Product, Greater-Than, Set-Disjointness, Gap-Hamming Distance etc. Our result also implies near optimal direct product results for several important functions and relations used to show exponential separations between classical and quantum communication complexity, for which near optimal lower bounds are provided using the rectangle bound, for example by Raz [1999], Gavinsky [2008] and Klartag and Regev [2011]. In fact we are not aware of any relation for which it is known that the smooth rectangle bound does not provide an optimal lower bound. This lower bound subsumes many of the other lower bound methods, for example the rectangle bound (a.k.a the corruption bound), the smooth discrepancy bound (a.k.a the γ_2 bound) which in turn subsumes the discrepancy bound, the subdistribution bound and the conditional min-entropy bound. We show our result using information theoretic arguments. A key tool we use is a sampling protocol due to Braverman [2012], in fact a modification of it used by Kerenidis, Laplante, Lerays, Roland and Xiao [2012].

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Broadcast Channel Games: Equilibrium Characterization and a MIMO MAC-BC Game Duality

The emergence of heterogeneous decentralized networks without a central controller, such as device-to-device communication systems, has created the need for new problem frameworks to design and analyze the performance of such networks. As a key step towards such an analysis for general networks, this paper examines the strategic behavior of \emph{receivers} in a Gaussian broadcast channel (BC) and \emph{transmitters} in a multiple access channel (MAC) with sum power constraints (sum power MAC) using the framework of non-cooperative game theory. These signaling scenarios are modeled as generalized Nash equilibrium problems (GNEPs) with jointly convex and coupled constraints and the existence and uniqueness of equilibrium achieving strategies and equilibrium utilities are characterized for both the Gaussian BC and the sum power MAC. The relationship between Pareto-optimal boundary points of the capacity region and the generalized Nash equilibria (GNEs) are derived for the several special cases and in all these cases it is shown that all the GNEs are Pareto-optimal, demonstrating that there is no loss in efficiency when players adopt strategic behavior in these scenarios. Several key equivalence relations are derived and used to demonstrate a game-theoretic duality between the Gaussian MAC and the Gaussian BC. This duality allows a parametrized computation of the equilibria of the BC in terms of the equilibria of the MAC and paves the way to translate several MAC results to the dual BC scenario.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Empirical Dynamic Programming

We propose empirical dynamic programming algorithms for Markov decision processes (MDPs). In these algorithms, the exact expectation in the Bellman operator in classical value iteration is replaced by an empirical estimate to get `empirical value iteration' (EVI). Policy evaluation and policy improvement in classical policy iteration are also replaced by simulation to get `empirical policy iteration' (EPI). Thus, these empirical dynamic programming algorithms involve iteration of a random operator, the empirical Bellman operator. We introduce notions of probabilistic fixed points for such random monotone operators. We develop a stochastic dominance framework for convergence analysis of such operators. We then use this to give sample complexity bounds for both EVI and EPI. We then provide various variations and extensions to asynchronous empirical dynamic programming, the minimax empirical dynamic program, and show how this can also be used to solve the dynamic newsvendor problem. Preliminary experimental results suggest a faster rate of convergence than stochastic approximation algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A direct product theorem for bounded-round public-coin randomized communication complexity

In this paper, we show a direct product theorm in the model of two-party bounded-round public-coin randomized communication complexity. For a relation f subset of X times Y times Z (X,Y,Z are finite sets), let R^{(t), pub}_e (f) denote the two-party t-message public-coin communication complexity of f with worst case error e. We show that for any relation f and positive integer k: R^{(t), pub}_{1 - 2^{-Omega(k/t^2)}}(f^k) = Omega(k/t (R^{(t), pub}_{1/3}(f) - O(t^2))) . In particular, it implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations f. Our result for example implies a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in [Jain 2011], where a strong direct product theorem for the two-party one-way public-coin communication complexity of all relations is shown (that is the special case of our result when t=1). One key tool used in our work and also in [Jain 2011] is a message compression technique due to [Braverman and Rao 2011], who used it to show a direct sum theorem for the two-party bounded-round public-coin randomized communication complexity of all relations. Another important tool that we use is a correlated sampling protocol, which for example, has been used in [Holenstein 2007] for proving a parallel repetition theorem for two-prover games.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Game Theoretic Model for the Gaussian Broadcast Channel

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. To characterize the strategic behavior of receivers connected to a single transmitter, this paper models the broadcast channel as a generalized Nash equilibrium problem with coupled constraints. The concept of normalized equilibrium (NoE) is used to characterize the equilibrium points and the existence and uniqueness of the NoE are proven for key scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A parallel approximation algorithm for mixed packing and covering semidefinite programs

We present a parallel approximation algorithm for a class of mixed packing and covering semidefinite programs which generalize on the class of positive semidefinite programs as considered by Jain and Yao [2011]. As a corollary we get a faster approximation algorithm for positive semidefinite programs with better dependence of the parallel running time on the approximation factor, as compared to that of Jain and Yao [2011]. Our algorithm and analysis is on similar lines as that of Young [2001] who considered analogous linear programs.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Coalitional Games for Transmitter Cooperation in MIMO Multiple Access Channels

Cooperation between nodes sharing a wireless channel is becoming increasingly necessary to achieve performance goals in a wireless network. The problem of determining the feasibility and stability of cooperation between rational nodes in a wireless network is of great importance in understanding cooperative behavior. This paper addresses the stability of the grand coalition of transmitters signaling over a multiple access channel using the framework of cooperative game theory. The external interference experienced by each TX is represented accurately by modeling the cooperation game between the TXs in \emph{partition form}. Single user decoding and successive interference cancelling strategies are examined at the receiver. In the absence of coordination costs, the grand coalition is shown to be \emph{sum-rate optimal} for both strategies. Transmitter cooperation is \emph{stable}, if and only if the core of the game (the set of all divisions of grand coalition utility such that no coalition deviates) is nonempty. Determining the stability of cooperation is a co-NP-complete problem in general. For a single user decoding receiver, transmitter cooperation is shown to be \emph{stable} at both high and low SNRs, while for an interference cancelling receiver with a fixed decoding order, cooperation is stable only at low SNRs and unstable at high SNR. When time sharing is allowed between decoding orders, it is shown using an approximate lower bound to the utility function that TX cooperation is also stable at high SNRs. Thus, this paper demonstrates that ideal zero cost TX cooperation over a MAC is stable and improves achievable rates for each individual user.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Correlation/Communication complexity of generating bipartite states

We study the correlation complexity (or equivalently, the communication complexity) of generating a bipartite quantum state $ρ$. When $ρ$ is a pure state, we completely characterize the complexity for approximately generating $ρ$ by a corresponding approximate rank, closing a gap left in Ambainis, Schulman, Ta-Shma, Vazirani and Wigderson (SIAM Journal on Computing, 32(6):1570-1585, 2003). When $ρ$ is a classical distribution $P(x,y)$, we tightly characterize the complexity of generating $P$ by the psd-rank, a measure recently proposed by Fiorini, Massar, Pokutta, Tiwary and de Wolf (STOC 2012). We also present a characterization of the complexity of generating a general quantum state $ρ$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Decentralized Learning for Multi-player Multi-armed Bandits

We consider the problem of distributed online learning with multiple players in multi-armed bandits (MAB) models. Each player can pick among multiple arms. When a player picks an arm, it gets a reward. We consider both i.i.d. reward model and Markovian reward model. In the i.i.d. model each arm is modelled as an i.i.d. process with an unknown distribution with an unknown mean. In the Markovian model, each arm is modelled as a finite, irreducible, aperiodic and reversible Markov chain with an unknown probability transition matrix and stationary distribution. The arms give different rewards to different players. If two players pick the same arm, there is a "collision", and neither of them get any reward. There is no dedicated control channel for coordination or communication among the players. Any other communication between the users is costly and will add to the regret. We propose an online index-based distributed learning policy called ${\tt dUCB_4}$ algorithm that trades off \textit{exploration v. exploitation} in the right way, and achieves expected regret that grows at most as near-$O(\log^2 T)$. The motivation comes from opportunistic spectrum access by multiple secondary users in cognitive radio networks wherein they must pick among various wireless channels that look different to different users. This is the first distributed learning algorithm for multi-player MABs to the best of our knowledge.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Dynamic Pricing of Power in Smart-Grid Networks

In this paper we introduce the problem of dynamic pricing of power for smart-grid networks. This is studied within a network utility maximization (NUM) framework in a deterministic setting with a single provider, multiple users and a finite horizon. The provider produces power or buys power in a (deterministic) spot market, and determines a dynamic price to charge the users. The users then adjust their demand in response to the time-varying prices. This is typically categorized as the demand response problem, and we study a progression of related models by focusing on two aspects: 1) the characterization of the structure of the optimal dynamic prices in the Smart Grid and the optimal demand and supply under various interaction with a spot market; 2) a greedy approach to facilitate the solution process of the aggregate NUM problem and the optimality gap between the greedy solution and the optimal one.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Short proofs of the Quantum Substate Theorem

The Quantum Substate Theorem due to Jain, Radhakrishnan, and Sen (2002) gives us a powerful operational interpretation of relative entropy, in fact, of the observational divergence of two quantum states, a quantity that is related to their relative entropy. Informally, the theorem states that if the observational divergence between two quantum states rho, sigma is small, then there is a quantum state rho' close to rho in trace distance, such that rho' when scaled down by a small factor becomes a substate of sigma. We present new proofs of this theorem. The resulting statement is optimal up to a constant factor in its dependence on observational divergence. In addition, the proofs are both conceptually simpler and significantly shorter than the earlier proof.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Stochastic dominance-constrained Markov decision processes

We are interested in risk constraints for infinite horizon discrete time Markov decision processes (MDPs). Starting with average reward MDPs, we show that increasing concave stochastic dominance constraints on the empirical distribution of reward lead to linear constraints on occupation measures. The optimal policy for the resulting class of dominance-constrained MDPs is obtained by solving a linear program. We compute the dual of this linear program to obtain average dynamic programming optimality equations that reflect the dominance constraint. In particular, a new pricing term appears in the optimality equations corresponding to the dominance constraint. We show that many types of stochastic orders can be used in place of the increasing concave stochastic order. We also carry out a parallel development for discounted reward MDPs with stochastic dominance constraints. The paper concludes with a portfolio optimization example.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Parallel Approximation Algorithm for Positive Semidefinite Programming

Positive semidefinite programs are an important subclass of semidefinite programs in which all matrices involved in the specification of the problem are positive semidefinite and all scalars involved are non-negative. We present a parallel algorithm, which given an instance of a positive semidefinite program of size N and an approximation factor eps > 0, runs in (parallel) time poly(1/eps) \cdot polylog(N), using poly(N) processors, and outputs a value which is within multiplicative factor of (1 + eps) to the optimal. Our result generalizes analogous result of Luby and Nisan [1993] for positive linear programs and our algorithm is inspired by their algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the power of a unique quantum witness

In a celebrated paper, Valiant and Vazirani raised the question of whether the difficulty of NP-complete problems was due to the wide variation of the number of witnesses of their instances. They gave a strong negative answer by showing that distinguishing between instances having zero or one witnesses is as hard as recognizing NP, under randomized reductions. We consider the same question in the quantum setting and investigate the possibility of reducing quantum witnesses in the context of the complexity class QMA, the quantum analogue of NP. The natural way to quantify the number of quantum witnesses is the dimension of the witness subspace W in some appropriate Hilbert space H. We present an efficient deterministic procedure that reduces any problem where the dimension d of W is bounded by a polynomial to a problem with a unique quantum witness. The main idea of our reduction is to consider the Alternating subspace of the d-th tensor power of H. Indeed, the intersection of this subspace with the d-th tensor power of W is one-dimensional, and therefore can play the role of the unique quantum witness.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Strategic Arrivals into Queueing Networks: The Network Concert Queueing Game

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. In the fluid limit derived, we then study the population game wherein users strategically choose when to arrive, and upon arrival which of the K queues to join. The queues start service at given times, which can potentially be different. We characterize the (strategic) arrival process at each of the queues, and the price of anarchy of the ensuing strategic arrival game. We then extend the analysis to multiple populations of users, each with a different cost metric. The equilibrium arrival profile and price of anarchy are derived. Finally, we present the methodology for exact equilibrium analysis. This, however, is tractable for only some simple cases such as two users arriving at a two node queueing network, which we then present.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The influence lower bound via query elimination

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function f in terms of the maximum influence of any variable of f. Our lower bound also applies to the two-sided error distributional query complexity of f, and it allows an immediate extension which can be used to prove stronger lower bounds for some functions.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A strong direct product theorem for two-way public coin communication complexity

We show a direct product result for two-way public coin communication complexity of all relations in terms of a new complexity measure that we define. Our new measure is a generalization to non-product distributions of the two-way product subdistribution bound of [J, Klauck and Nayak 08], thereby our result implying their direct product result in terms of the two-way product subdistribution bound. We show that our new complexity measure gives tight lower bound for the set-disjointness problem, as a result we reproduce strong direct product result for this problem, which was previously shown by [Klauck 00].

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

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

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. We consider in this work a broad class of multi-armed bandits with dependent arms that yield rewards as a linear combination of a set of unknown parameters. For this general framework, we present efficient policies that are shown to achieve regret that grows logarithmically with time, and polynomially in the number of unknown parameters (even though the number of dependent arms may grow exponentially). Furthermore, these policies only require storage that grows linearly in the number of unknown parameters. We show that this generalization is broadly applicable and useful for many interesting tasks in networks that can be formulated as tractable combinatorial optimization problems with linear objective functions, such as maximum weight matching, shortest path, and minimum spanning tree computations.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity

Let f subset of X x Y x Z be a relation. Let the public coin one-way communication complexity of f, with worst case error 1/3, be denoted R^{1,pub}_{1/3}(f). We show that if for computing f^k (k independent copies of f), o(k R^{1,pub}_{1/3}(f)) communication is provided, then the success is exponentially small in k. This settles the strong direct product conjecture for all relations in public coin one-way communication complexity. We show a new tight characterization of public coin one-way communication complexity which strengthens on the tight characterization shown in [J., Klauck, Nayak 08]. We use the new characterization to show our direct product result and this may also be of independent interest.

0 citations0 reviewsNo code linkedOpen access