With Retrieval-Augmented Generation (RAG) becoming more and more prominent in generative AI solutions, there is an emerging need for systematically evaluating its effectiveness. We introduce the LiveRAG benchmark, a publicly available dataset of 895 synthetic questions and answers designed to support systematic evaluation of RAG-based Q&A systems. This synthetic benchmark is derived from the one used during the SIGIR'2025 LiveRAG challenge, where competitors were evaluated under strict time constraints. It is augmented with information that was not made available to competitors during the challenge, such as the ground-truth answers, together with their associated supporting claims which were used for evaluating competitors' answers. In addition, each question is associated with estimated difficulty and discriminability scores, derived from applying an Item Response Theory model to competitors' responses. Our analysis highlights the benchmark's question diversity, the wide range of difficulty levels, and their usefulness in differentiating between system capabilities. The LiveRAG benchmark will hopefully help the community advance RAG research, conduct systematic evaluation, and develop more robust Q&A systems.

The subset selection problem is fundamental in machine learning and other fields of computer science. We introduce a stochastic formulation for the minimum cost subset selection problem in a black box setting, in which only the subset metric value is available. Subsequently, we can handle two-stage schemes, with an outer subset-selection component and an inner subset cost evaluation component. We propose formulating the subset selection problem in a stochastic manner by choosing subsets at random from a distribution whose parameters are learned. Two stochastic formulations are proposed. The first explicitly restricts the subset's cardinality, and the second yields the desired cardinality in expectation. The distribution is parameterized by a decision variable, which we optimize using Stochastic Mirror Descent. Our choice of distributions yields constructive closed-form unbiased stochastic gradient formulas and convergence guarantees, including a rate with favorable dependency on the problem parameters. Empirical evaluation of selecting a subset of layers in transfer learning complements our theoretical findings and demonstrates the potential benefits of our approach.

The LiveRAG Challenge at SIGIR 2025 provides a competitive platform for advancing Retrieval-Augmented Generation (RAG) technologies. Participants from academia and industry have been invited to build a RAG-based question answering system using a fixed corpus (Fineweb-10BT) and a common open-source LLM (Falcon3-10B-Instruct). The goal is to enable fair, focused comparisons on retrieval and prompting strategies. During the Live Challenge Day, the competing teams must provide answers and supportive information to 500 unseen questions within a strict two-hour window. Evaluation is conducted in two stages: automated LLM-as-a-judge scoring mechanism for correctness and faithfulness, followed by a manual review of top ranked submissions. The winners will be announced and prizes awarded during the LiveRAG Workshop at SIGIR 2025 in Padua, Italy.

Factorization machine (FM) variants are widely used in recommendation systems that operate under strict throughput and latency requirements, such as online advertising systems. FMs have two prominent strengths. First, is their ability to model pairwise feature interactions while being resilient to data sparsity by learning factorized representations. Second, their computational graphs facilitate fast inference and training. Moreover, when items are ranked as a part of a query for each incoming user, these graphs facilitate computing the portion stemming from the user and context fields only once per query. Thus, the computational cost for each ranked item is proportional only to the number of fields that vary among the ranked items. Consequently, in terms of inference cost, the number of user or context fields is practically unlimited.

With yearly revenue exceeding one billion USD, Yahoo Gemini native advertising marketplace serves more than two billion impressions daily to hundreds of millions of unique users. One of the fastest growing segments of Gemini native is dynamic-product-ads (DPA), where major advertisers, such as Amazon and Walmart, provide catalogs with millions of products for the system to choose from and present to users. The subject of this work is finding and expanding the right audience for each DPA ad, which is one of the many challenges DPA presents. Approaches such as targeting various user groups, e.g., users who already visited the advertisers’ websites (Retargeting), users that searched for certain products (Search-Prospecting), or users that reside in preferred locations (Location-Prospecting), have limited audience expansion capabilities.In this work we present two new approaches for audience expansion that also maintain predefined performance goals. The Conversion-Prospecting approach predicts DPA conversion rates based on Gemini native logged data, and calculates the expected cost-per-action (CPA) for determining users’ eligibility to products and optimizing DPA bids in Gemini native auctions. To support new advertisers and products, the Trending-Prospecting approach matches trending products to users by learning their tendency towards products from advertisers’ sites logged events. The tendency scores indicate the popularity of the product and the similarity of the user to those who have previously engaged with this product.The two new prospecting approaches were tested online, serving real Gemini native traffic, demonstrating impressive DPA delivery and DPA revenue lifts while maintaining most traffic within the acceptable CPA range (i.e., performance goal). In particular, we measure 10% delivery lift and 1.58% revenue lift for Conversion-Prospecting, and almost 13% delivery lift and 6.33% revenue lift for Trending-Prospecting. After a successful testing phase, the proposed approaches are currently in production and serve all Gemini native traffic.

Yahoo Gemini native advertising marketplace serves billions of impressions daily, to hundreds millions of unique users, and reaches a yearly revenue of hundreds of millions USDs. Powering Gemini native models for predicting advertise (ad) event probabilities, such as conversions and clicks, is OFFSET - a feature enhanced collaborative-filtering (CF) based event prediction algorithm. The predicted probabilities are then used in Gemini native auctions to determine which ads to present for every serving event (impression). Dynamic creative optimization (DCO) is a recent Gemini native product that was launched two years ago and is increasingly gaining more attention from advertisers. The DCO product enables advertisers to issue several assets per each native ad attribute, creating multiple combinations for each DCO ad. Since different combinations may appeal to different crowds, it may be beneficial to present certain combinations more frequently than others to maximize revenue while keeping advertisers and users satisfied. The initial DCO offer was to optimize click-through rates (CTR), however as the marketplace shifts more towards conversion based campaigns, advertisers also ask for a conversion based solution. To accommodate this request, we present a post-auction solution, where DCO ads’ combinations are favored according to their predicted conversion rate (CVR). The predictions are provided by an auxiliary OFFSET based combination CVR prediction model, and used to generate the combination distributions for DCO ad rendering during serving time. An online evaluation of this explore-exploit like solution, via online bucket A/B testing, serving Gemini native DCO traffic, showed a 53.5% CVR lift, when compared to a control bucket serving all combinations uniformly at random. The impressive results demonstrate the ability of this practical yet effective solution to overcome many real-life issues such as data sparsity, reporting delays, trends, and various system constraints. The CVR prediction based DCO system is now fully deployed, serving all Gemini native traffic.

Ad click-though rate prediction (pCTR) is one of the core tasks of online advertising. Driving the pCTR models of Yahoo Gemini native advertising is OFFSET - a feature enhanced collaborative-filtering based event prediction algorithm. Due to data sparsity issues OFFSET models both users and items by mapping their features into a latent space, where the resulting user vector is a non-linear function of the user feature vectors (e.g., age, gender, hour, etc.) which allows pairwise dependencies. This pairwise dependencies concept is also used by other algorithms such as the Field-aware Factorization Machines (FFM). However, both in OFFSET and in FFM, the different pairwise interactions are modeled by latent vectors of constant and equal lengths. When prediction models are used online for serving real traffic, where the total serving model size is often limited, a non uniform representation of the pairwise interactions should be considered in order to maximize the accuracy of the model while consuming the same or even less space. In this work we present a Dynamic Length Factorization Machines (DLFM) algorithm that dynamically optimizes the length of the vectors for each feature interaction during training, while not exceeding a maximal overall latent vector size. After showing good online performance of 1.46% revenue lift and a 2.15% CTR lift, serving Gemini native traffic, the DLFM was pushed into production. Since integrated into production, the DLFM has not only improved the accuracy of the model by optimizing the length of each latent space, but has also reduced the total size of the model by 25%. Although the algorithm was applied to OFFSET, we show that DLFM can be applied to any FFM-like algorithm to optimize its pairwise feature vector lengths. We also present an Educated Model Initialization - a novel mechanism for initializing a new model based on an existing model that has some mutual user features. Using this mechanism, we managed to reduce the training time of our models by more than 90% when compared to an equivalent model that is trained from "scratch".

Verizon Media (VZM) native advertising is one of VZM largest and fastest growing businesses, reaching a run-rate of several hundred million USDs in the past year. Driving the VZM native models that are used to predict event probabilities, such as click and conversion probabilities, is OFFSET - a feature enhanced collaborative-filtering based event-prediction algorithm. In this work we focus on the challenge of predicting click-through rates (CTR) when we are aware that some of the clicks have short dwell-time and are defined as accidental clicks. An accidental click implies little affinity between the user and the ad, so predicting that similar users will click on the ad is inaccurate. Therefore, it may be beneficial to remove clicks with dwell-time lower than a predefined threshold from the training set. However, we cannot ignore these positive events, as filtering these will cause the model to under predict. Previous approaches have tried to apply filtering and then adding corrective biases to the CTR predictions, but did not yield revenue lifts and therefore were not adopted. In this work, we present a new approach where the positive weight of the accidental clicks is distributed among all of the negative events (skips), based on their likelihood of causing accidental clicks, as predicted by an auxiliary model. These likelihoods are taken as the correct labels of the negative events, shifting our training from using only binary labels and adopting a binary cross-entropy loss function in our training process. After showing offline performance improvements, the modified model was tested online serving VZM native users, and provided 1.18% revenue lift over the production model which is agnostic to accidental clicks.

Verizon media (VZM) native advertising serves billions of impressions daily, reaching a yearly run-rate of many hundred of million USD. Driving VZM native models for predicting advertise (ad) event probabilities, such as clicks and conversions, is OFFSET - a feature enhanced collaborative-filtering ( CF) based e vent prediction algorithm. The predicted probabilities are then used in VZM native auctions to determine which ads to present for each serving event. Dynamic creative optimization (DCO) is a new VZM native product that was launched recently and is gaining increasingly more attention from advertisers. The DCO product allows advertisers to provide several assets per each native ad attribute, creating a plurality of combinations for each DCO ad. Since different combinations may appeal to different crowds, it may be beneficial to present certain combinations more frequently than others to maximize revenue. Inspired by the success of our Carousel asset optimization product, we present a post-auction successive elimination based approach for ranking DCO combinations according to their measured click through rates (CTR). This reinforcement learning multi-arm bandit like solution was evaluated during an online beta test phase done with selected advertisers, showing 21.8% CTR and 21.5% revenue lifts over a control bucket serving all combinations uniformly at random. The good performance of our DCO product attracts advertisers and it already shows a yearly run-rate of several million USD in revenue.

Online advertising systems often provide means for users to close ads and also leave feedback. Although closing ads requires additional user engagement and usually indicates a poor user experience, ad closes are not as scarce as one might expect. Recently it was shown that penalizing ads with high closing likelihood during auctions may substantially reduce the number of ad closes while maintaining a small predefined revenue loss. In this work, we focus on email since this is the property in which most ad closes occur. Using data collected from a major email provider, we present interesting insights about the interplay between ad closes in email and email-related user actions. In particular, we explore the merits of integrating information derived from user actions in email for ad-close prediction. Thorough performance evaluation reveals that incorporating such signals significantly improves ad-close prediction quality over previously reported results.

Verizon Media native advertising (also known as Yahoo Gemini native) serves billions of ad impressions daily, reaching several hundreds of millions USD in revenue yearly. Although we strive to provide the best experience for our users, there will always be some users that dislike our ads in certain cases. To address these situations Gemini native platform provides an ad close mechanism that enables users to close ads that they dislike and also to provide a reasoning for their action. Surprisingly, users do care about their ad experience and their engagement with the ad close mechanism is quite significant. While the ad close rate (ACR) is lower than the click through rate (CTR), they are of the same order of magnitude, especially on Yahoo mail properties. Since ad close events indicate bad user experience caused mostly by poor ad quality, we would like to exploit the ad close signals to improve user experience and reduce the number of ad close events while maintaining a predefined total revenue loss.

Yahoo's native advertising (also known as Gemini native) serves billions of ad impressions daily, reaching a yearly run-rate of many hundred of millions USD. Driving the Gemini native models that are used to predict both click probability (pCTR) and conversion probability (pCONV) is øffset\ -- a feature enhanced collaborative-filtering (CF) based event prediction algorithm. øffset is a one-pass algorithm that updates its model for every new batch of logged data using a stochastic gradient descent (SGD) based approach. Since øffset represents its users by their features (i.e., user-less model) due to sparsity issues, rule based hard frequency capping (HFC) is used to control the number of times a certain user views a certain ad. Moreover, related statistics reveal that user ad fatigue results in a dramatic drop in click through rate (CTR). Therefore, to improve click prediction accuracy, we propose a soft frequency capping (SFC) approach, where the frequency feature is incorporated into the øffset model as a user-ad feature and its weight vector is learned via logistic regression as part of øffset training. Online evaluation of the soft frequency capping algorithm via bucket testing showed a significant $7.3$% revenue lift. Since then, the frequency feature enhanced model has been pushed to production serving all traffic, and is generating a hefty revenue lift for Yahoo Gemini native. We also report related statistics that reveal, among other things, that while users' gender does not affect ad fatigue, the latter seems to increase with users' age.

Yahoo's native advertising marketplace (also known as Gemini native) serves billions of ad impressions daily, reaching many hundreds of millions USD in yearly revenue. Driving Gemini native models that are used to predict ad click probability (pCTR) is OFFSET - a feature enhanced collaborative-filtering (CF) based event prediction algorithm. While some of the user features used by OFFSET have high coverage, other features, especially those based on click patterns, suffer from extremely low coverage. In this work, we present a framework that simplifies complex interactions between users and other entities in a bipartite graph. The one mode projection of this bipartite graph onto users represents a user similarity network, allowing us to quantify similarities between users. This network is combined with existing user features to create an enhanced feature set. In particular, we describe the implementation and performance of our framework using user Internet browsing data (e.g., visited pages URLs) to enhance the user category feature. Using our framework we effectively increase the feature coverage by roughly 15%. Moreover, online results evaluated on 1% of Gemini native traffic show that using the enhanced feature increases revenue by almost 1% when compared to the baseline operating with the original feature, which is a substantial increase at scale.

Yahoo's native advertising (also known as Gemini native) serves billions of ad impressions daily, reaching a yearly run-rate of many hundred of millions USD. Driving Gemini native models for predicting both click probability (pCTR) and conversion probability (pCONV) is OFFSET - a feature enhanced collaborative-filtering (CF) based event prediction algorithm. The predicted pCTRs are then used in Gemini native auctions to determine which ads to present for each serving event. A fast growing segment of Gemini native is Carousel ads that include several cards (or assets) which are used to populate several slots within the ad. Since Carousel ad slots are not symmetrical and some are more conspicuous than others, it is beneficial to render assets to slots in a way that maximizes revenue.

The item cold-start problem is inherent to collaborative filtering (CF) recommenders where items and users are represented by vectors in a latent space. It emerges since CF recommenders rely solely on historical user interactions to characterize their item inventory. As a result, an effective serving of new and trendy items to users may be delayed until enough user feedback is received, thus, reducing both users' and content suppliers' satisfaction. To mitigate this problem, many commercial recommenders apply random exploration and devote a small portion of their traffic to explore new items and gather interactions from random users. Alternatively, content or context information is combined into the CF recommender, resulting in a hybrid system. Another hybrid approach is to learn a mapping between the item attribute space and the CF latent feature space, and use it to characterize the new items providing initial estimates for their latent vectors.

The item cold-start problem is of a great importance in collaborative filtering (CF) recommendation systems. It arises when new items are added to the inventory and the system cannot model them properly since it relies solely on historical users' interactions (e.g., ratings). Much work has been devoted to mitigate this problem mostly by employing hybrid approaches that combine content-based recommendation techniques or by devoting a portion of the user traffic for exploration to gather interactions from random users. We focus on pure CF recommender systems (i.e., without content or context information) in a realistic online setting, where random exploration is inefficient and smart exploration that carefully selects users is crucial due to the huge flux of new items with short lifespan. We further assume that users arrive randomly one after the other and that the system has to immediately decide whether the arriving user will participate in the exploration of the new items.

It is well known that collaborative filtering (CF) based recommender systems provide better modeling of users and items associated with considerable rating history. The lack of historical ratings results in the user and the item cold-start problems. The latter is the main focus of this work. Most of the current literature addresses this problem by integrating content-based recommendation techniques to model the new item. However, in many cases such content is not available, and the question arises is whether this problem can be mitigated using CF techniques only. We formalize this problem as an optimization problem: given a new item, a pool of available users, and a budget constraint, select which users to assign with the task of rating the new item in order to minimize the prediction error of our model. We show that the objective function is monotone-supermodular, and propose efficient optimal design based algorithms that attain an approximation to its optimum. Our findings are verified by an empirical study using the Netflix dataset, where the proposed algorithms outperform several baselines for the problem at hand.

We study the problem of exploration in stochastic Multi-Armed Bandits. Even in the simplest setting of identifying the best arm, there remains a logarithmic multiplicative gap between the known lower and upper bounds for the number of arm pulls required for the task. This extra logarithmic factor is quite meaningful in nowadays large-scale applications. We present two novel, parameter-free algorithms for identifying the best arm, in two different settings: given a target confidence and given a target budget of arm pulls, for which we prove upper bounds whose gap from the lower bound is only doubly-logarithmic in the problem parameters. We corroborate our theoretical results with experiments demonstrating that our algorithm outperforms the state-of-the-art and scales better as the size of the problem increases.

We study exploration in Multi-Armed Bandits (MAB) in a setting where~$k$ players collaborate in order to identify an $\epsilon$-optimal arm. Our motivation comes from recent employment of MAB algorithms in computationally intensive, large-scale applications. Our results demonstrate a non-trivial tradeoff between the number of arm pulls required by each of the players, and the amount of communication between them. In particular, our main result shows that by allowing the $k$ players to communicate \emph{only once}, they are able to learn $\sqrt{k}$ times faster than a single player. That is, distributing learning to $k$ players gives rise to a factor~$\sqrt{k}$ parallel speed-up. We complement this result with a lower bound showing this is in general the best possible. On the other extreme, we present an algorithm that achieves the ideal factor $k$ speed-up in learning performance, with communication only logarithmic in~$1/\epsilon$.

In the Internet music scene, where recommendation technology is key for navigating huge collections, large market players enjoy a considerable advantage. Accessing a wider pool of user feedback leads to an increasingly more accurate analysis of user tastes, effectively creating a "rich get richer" effect. This work aims at significantly lowering the entry barrier for creating music recommenders, through a paradigm coupling a public data source and a new collaborative filtering (CF) model. We claim that Internet radio stations form a readily available resource of abundant fresh human signals on music through their playlists, which are essentially cohesive sets of related tracks. In a way, our models rely on the knowledge of a diverse group of experts in lieu of the commonly used wisdom of crowds. Over several weeks, we aggregated publicly available playlists of thousands of Internet radio stations, resulting in a dataset encompassing millions of plays, and hundreds of thousands of tracks and artists. This provides the large scale ground data necessary to mitigate the cold start problem of new items at both mature and emerging services.

Bucket testing, also known as split testing, A/B testing, or 0/1 testing, is a widely used method for evaluating users' satisfaction with new features, products, or services. In order not to expose the whole user base to the new service, the mean user satisfaction rate is estimated by exposing the service only to a few uniformly chosen random users. In a recent work, Backstrom and Kleinberg, defined the notion of network bucket testing for social services. In this context, users' interactions are only valid for measurement if some minimal number of their friends are also given the service. The goal is to estimate the mean user satisfaction rate while providing the service to the least number of users. This constraint makes uniform sampling, which is optimal for the traditional case, grossly inefficient. In this paper we introduce a simple general framework for designing and evaluating sampling techniques for network bucket testing. The framework is constructed in a way that sampling algorithms are only required to generate sets of users to which the service should be provided. Given an algorithm, the framework produces an unbiased user satisfaction rate estimator and a corresponding variance bound for any network and any user satisfaction function. Furthermore, we present several simple sampling algorithms that are evaluated using both synthetic and real social networks. Our experiments corroborate the theoretical results and demonstrate the effectiveness of the proposed framework and algorithms.

Online social networks have become very popular in recent years and their number of users is already measured in many hundreds of millions. For various commercial and sociological purposes, an independent estimate of their sizes is important. In this work, algorithms for estimating the number of users in such networks are considered. The proposed schemes are also applicable for estimating the sizes of networks' sub-populations. The suggested algorithms interact with the social networks via their public APIs only, and rely on no other external information. Due to obvious traffic and privacy concerns, the number of such interactions is severely limited. We therefore focus on minimizing the number of API interactions needed for producing good size estimates. We adopt the abstraction of social networks as undirected graphs and use random node sampling. By counting the number of collisions or non-unique nodes in the sample, we produce a size estimate. Then, we show analytically that the estimate error vanishes with high probability for smaller number of samples than those required by prior-art algorithms. Moreover, although our algorithms are provably correct for any graph, they excel when applied to social network-like graphs. The proposed algorithms were evaluated on synthetic as well real social networks such as Facebook, IMDB, and DBLP. Our experiments corroborated the theoretical results, and demonstrated the effectiveness of the algorithms.

Modern search engines are expected to make documents searchable shortly after they appear on the ever changing Web. To satisfy this requirement, the Web is frequently crawled. Due to the sheer size of their indexes, search engines distribute the crawled documents among thousands of servers in a scheme called local index-partitioning, such that each server indexes only several million pages. To ensure documents from the same host (e.g., www.nytimes.com) are distributed uniformly over the servers, for load balancing purposes, random routing of documents to servers is common. To expedite the time documents become searchable after being crawled, documents may be simply appended to the existing index partitions. However, indexing by merely appending documents, results in larger index sizes since document reordering for index compactness is no longer performed. This, in turn, degrades search query processing performance which depends heavily on index sizes.

A source communicates with a remote destination via a number of distributed relays. Communication from source to relays takes place over a (discrete or Gaussian) broadcast channel, while the relays are connected to the receiver via orthogonal finite-capacity links. Unknowns to the source and relays, link failures may occur between any subset of relays and the destination in a nonergodic fashion. Upper and lower bounds are derived on average achievable rates with respect to the prior distribution of the link failures, assuming the relays to be oblivious to the source codebook. The lower bounds are obtained by proposing strategies that combine the broadcast coding approach, previously investigated for quasi-static fading channels, and different robust distributed compression techniques. Numerical results show that lower and upper bounds are quite close over most operating regimes, and provide insight into optimal transmission design choices for the scenario at hand. Extension to the case of nonoblivious relays is also discussed.

This work studies the throughput scaling laws of ad hoc wireless networks in the limit of a large number of nodes. A random connections model is assumed in which the channel connections between the nodes are drawn independently from a common distribution. Transmitting nodes are subject to an on-off strategy, and receiving nodes employ conventional single-user decoding. The following results are proven: 1) for a class of connection models with finite mean and variance, the throughput scaling is upper-bounded by O(n1/3) for single-hop schemes, and O(n1/2) for two-hop (and multihop) schemes; 2) the Θ(n1/2) throughput scaling is achievable for a specific connection model by a two-hop opportunistic relaying scheme, which employs full, but only local channel state information (CSI) at the receivers, and partial CSI at the transmitters; 3) by relaxing the constraints of finite mean and variance of the connection model, linear throughput scaling Θ(n) is achievable with Pareto-type fading models.

In this paper, the performance of cellular networks with joint multicell processing and dedicated relay terminals is investigated. It is assumed that each relay terminal is capable of full-duplex operation and receives the transmission of relay terminals in adjacent cells. Focusing on intra-cell time division multiple access and non-fading channels, a simplified relay-aided uplink cellular model is considered. Addressing the achievable per-cell sum-rate, two non-regenerative relaying schemes are considered. Interpreting the received signal at the base stations as the outcome of a two-dimensional linear time invariant system, the multicell processing rate of an amplify-and-forward scheme is derived and shown to decrease with the inter-relay interference level. A novel form of distributed compress-and-forward scheme with decoder side information is then proposed. The corresponding multicell processing rate, which is given as a solution of a simple fixed-point equation, reveals that the compress-and-forward scheme is able to completely eliminate the inter-relay interference, and it approaches a "cut-set-like" upper bound for strong relay terminal transmission power. The benefits of base-station cooperation via multicell processing over the conventional single site processing approach is also demonstrated for both protocols.

This paper studies the throughput scaling of wireless networks over channels with random connections, in which the channel connections are independent and identically distributed (i.i.d.) according to a common distribution. The channel distribution is quite general, with the only limitations being that the mean and variance are finite. Previous works have shown that, when channel state information (CSI) of the entire network is known a priori to all the nodes, wireless networks are degrees-of- freedom limited rather than interference limited. In this work, we show that this is not the case with a less demanding CSI assumption. Specifically, we quantify the throughput scaling for different communication protocols under the assumption of perfect receiver CSI and partial transmitter CSI (via feedback). It is shown that the throughput of single-hop and two-hop schemes are upper-bounded by respectively, O(n1/3) and O(n1/2), where n is the total number of source-to-destination pairs. In addition, multihop schemes cannot do better than the two-hop relaying scheme. Furthermore, the achievability of the Theta(n1/2) scaling for the two-hop scheme is demonstrated by a constructive example.

A multi-relay network is considered in which communication from source to relays takes place over a (discrete or Gaussian) broadcast channel, while the relays are connected to the receiver via orthogonal finite-capacity links. Unbeknownst to the source and relays, link failures may take place between any subset of relays and destination in a non-ergodic fashion. Upper and lower bounds are derived on average achievable rates with respect to the prior distribution of the link failures, assuming the relays to be oblivious to the source codebook. The lower bounds are obtained via strategies that combine the broadcast coding approach, previously investigated for quasi-static fading channels, and various robust distributed compression techniques.

Relay networks having n source-to-destination pairs and m half-duplex relays, all operating in the same frequency band and in the presence of block fading, are analyzed. This setup has attracted significant attention, and several relaying protocols have been reported in the literature. However, most of the proposed solutions require either centrally coordinated scheduling or detailed channel state information (CSI) at the transmitter side. Here, an opportunistic relaying scheme is proposed that alleviates these limitations, without sacrificing the system throughput scaling in the regime of large n. The scheme entails a two-hop communication protocol, in which sources communicate with destinations only through half-duplex relays. All nodes operate in a completely distributed fashion, with no cooperation. The key idea is to schedule at each hop only a subset of nodes that can benefit from multiuser diversity. To select the source and destination nodes for each hop, CSI is required at receivers (relays for the first hop, and destination nodes for the second hop), and an index-valued CSI feedback at the transmitters. For the case when n is large and m is fixed, it is shown that the proposed scheme achieves a system throughput of m/2 bits/s/Hz. In contrast, the information-theoretic upper bound of (m/2) log log n bits/s/Hz is achievable only with more demanding CSI assumptions and cooperation between the relays. Furthermore, it is shown that, under the condition that the product of block duration and system bandwidth scales faster than log n log log n, the achievable throughput of the proposed scheme scales as Theta (log n). Notably, this is proven to be the optimal throughput scaling even if centralized scheduling is allowed, thus proving the optimality of the proposed scheme in the scaling law sense. Simulation results indicate a rather fast convergence to the asymptotic limits with the system's size, demonstrating the practical importance of the scaling results.

In this paper we study the spectrum of certain large random HermitianJacobimatrices. These matrices are known to describe certain communication setups. In particular, we are interested in an uplink cellular channel which models mobile users experiencing a soft-handoff situation under joint multicell decoding. Considering rather general fading statistics we provide a closed-form expression for the per-cell sum-rate of this channel in high signal-to-noise ratio (SNR), when an intra-cell time-division multiple-access (TDMA) protocol is employed. Since the matrices of interest aretridiagonal, their eigenvectors can be considered as sequences with second-order linear recurrence. Therefore, the problem is reduced to the study of the exponential growth of products of two-by-two matrices. For the case whereKusers are simultaneously active in each cell, we obtain a series of lower and upper bound on the high-SNR power offset of the per-cell sum-rate, which are considerably tighter than previously known bounds.

In this work, new achievable rates are derived for the uplink channel of a cellular network with joint multicell processing (MCP), where unlike previous results, the ideal backhaul network has finite capacity per cell. Namely, the cell sites are linked to the central joint processor via lossless links with finite capacity. The new rates are based on compress-and-forward schemes combined with local decoding. Further, the cellular network is abstracted by symmetric models, which render analytical treatment plausible. For this family of idealistic models, achievable rates are presented for both Gaussian and fading channels. The rates are given in closed form for the classical Wyner model and the soft-handover model. These rates are then demonstrated to be rather close to the optimal unlimited backhaul joint processing rates, even for modest backhaul capacities, supporting the potential gain offered by the joint MCP approach. Particular attention is also given to the low-signal-to-noise ratio (SNR) characterization of these rates through which the effect of the limited backhaul network is explicitly revealed. In addition, the rate at which the backhaul capacity should scale in order to maintain the original high-SNR characterization of an unlimited backhaul capacity system is found.

Cooperative decoding at the base stations (or access points) of an infrastructure wireless network is currently well recognized as a promising approach for intercell interference mitigation, thus enabling high frequency reuse. Deployment of cooperative multicell decoding depends critically on the tolopology and quality of the available backhaul links connecting the base stations. This work studies a scenario where base stations are connected only if in adjacent cells, and via finite-capacity links. Relying on a linear Wyner-type cellular model with no fading, achievable rates are derived for the two scenarios where base stations are endowed only with the codebooks of local (in-cell) mobile stations, or also with the codebooks used in adjacent cells. Moreover, both uni- and bidirectional backhaul links are considered. The analysis sheds light on the impact of codebook information, decoding delay, and network planning (frequency reuse) on the performance of multicell decoding as enabled by local and finite-capacity backhaul links. Analysis in the high-signal-to-noise ratio (SNR) regime and numerical results validate the main conclusions.

A single source communicates with a single destination via a remote wireless multiple-antenna (multiple-input multiple-output (MIMO)) transceiver. The source has access to each of the transmit antennas through a finite-capacity link, and likewise the destination is connected to the receiving antennas via capacity-constrained channels (e.g., as for wired or time-division multiple access (TDMA) channels). Targeting a nomadic communication scenario, in which the remote MIMO transceiver is designed to serve different standards or services, it is assumed that transmitters and receivers are oblivious to the encoding function shared by source and destination. Assuming a Gaussian symmetric interference network as the channel model (as for regularly placed transmitters and receivers), achievable rates are investigated and compared with an upper bound (that holds also for codebook-dependent operation). Closed-form expressions are derived for large numbers of antennas (and in some cases large signal-to-noise ratios (SNRs)), and asymptotics of the achievable rates are studied with respect to either link capacities or SNR. Overall, the analysis points to effective transmission/reception strategies for the distributed MIMO channel at hand, which are optimal under specified conditions. In particular, it is concluded that in certain asymptotic and nonasymptotic regimes there is no loss of optimality in designing the system for nomadic applications (i.e., assuming oblivious transmitters and receivers). Numerical results validate the analysis.

In this work, a multicell cooperative zero-forcing beamforming (ZFBF) scheme combined with a simple user selection procedure is considered for the Wyner cellular downlink channel. The approach is to transmit to the user with the ldquobestrdquo local channel in each cell. The performance of this suboptimal scheme is investigated in terms of the conventional sum-rate scaling law and the sum-rate offset for an increasing number of users per cell. We term this characterization of the sum-rate for large number of users ashigh-loadregimecharacterization, and point out the similarity of this approach to the standard affine approximation used in the high-signal-to-noise ratio (SNR) regime. It is shown that, under an overall power constraint, the suboptimal cooperative multicell ZFBF scheme achieves the same sum-rate growth rate and slightly degraded offset law, when compared to an optimal scheme deploying joint multicell dirty-paper coding (DPC), asymptotically with the number of users per cell. Moreover, the overall power constraint is shown to ensure in probability, equal per-cell power constraints when the number of users per-cell increases.

A network consisting of n source-destination pairs and m relays with no direct link between source and destination nodes, is considered. Focusing on the large system limit (large n), the throughput scaling laws of two-hop relaying protocols are studied for Rayleigh fading channels. It is shown that, under the practical constraints of single-user encoding-decoding scheme, and partial channel state information (CSI) at the transmitters (via integer-value feedback from the receivers), the maximal throughput scales as log n even if joint scheduling among relays is allowed. Furthermore, a novel opportunistic relaying scheme with receiver CSI, partial transmitter CSI, and decentralized relay scheduling, is shown to achieve the optimal throughput scaling law of log n.

In this paper we study the spectrum of certain large random Hermitian Jacobi matrices. These matrices are known to describe certain communication setups. In particular we are interested in an uplink cellular channel which models mobile users experiencing a soft-handoff situation under joint multicell decoding. Considering rather general fading statistics we provide a closed form expression for the per-cell sum-rate of this channel in high-SNR, when an intra-cell TDMA protocol is employed. Since the matrices of interest are tridiagonal, their eigenvectors can be considered as sequences with second order linear recurrence. Therefore, the problem is reduced to the study of the exponential growth of products of two by two matrices. For the case where K users are simultaneously active in each cell, we obtain a series of lower and upper bounds on the high-SNR power offset of the per-cell sum-rate, which are considerably tighter than previously known bounds.

A scenario in which a single source communicates with a single destination via a distributed MIMO transceiver is considered. The source operates each of the transmit antennas via finite-capacity links, and likewise the destination is connected to the receiving antennas through capacity-constrained channels. Targeting a nomadic communication scenario, in which the distributed MIMO transceiver is designed to serve different standards or services, transmitters and receivers are assumed to be oblivious to the encoding functions shared by source and destination. Adopting a Gaussian symmetric interference network as the channel model (as for regularly placed transmitters and receivers), achievable rates are investigated and compared with an upper bound. It is concluded that in certain asymptotic and non-asymptotic regimes obliviousness of transmitters and receivers does not cause any loss of optimality.

In this paper the advantages provided by multi-cell processing of signals transmitted by mobile terminals (MTs) which are received via dedicated relay terminals (RTs) are studied. It is assumed that each RT is capable of full-duplex operation and receives the transmission of adjacent relay terminals. Focusing on intra-cell TDMA and non-fading channels, a simplified relay-aided uplink cellular model based on a model introduced by Wyner is considered. Assuming a nomadic application in which the RTs are oblivious to the MTs’ codebooks, a form of distributed compress-and-forward (CF) scheme with decoder side information is employed. The per-cell sum-rate of the CF scheme is derived and is given as a solution of a simple fixed point equation. This achievable rate reveals that the CF scheme is able to completely eliminate the inter-relay interference, and it approaches a “cut-set-like” upper bound for strong RTs transmission power. The CF rate is also shown to surpass the rate of an amplify-and-forward scheme via numerical calculations for a wide range of the system parameters.

Recent information theoretic results on cooperation in cellular systems are reviewed, addressing both multicell processing (cooperation among base stations) and relaying (cooperation at the user level). Two central issues are addressed, namely, first multicell processing is studied with either limited-capacity backhaul links to a central processor or only local (and finite-capacity) cooperation among neighboring cells. The role of codebook information, decoding delay and network planning (frequency reuse) are specifically highlighted along with the impact of different transmission/ reception strategies. Next, multicell processing is considered in the presence of cooperation at the user level, focusing on both out-of-band relaying via conferencing users and in-band relaying by means of dedicated relays. Non-fading and fading uplink and downlink channels adhering to simple Wyner-type, cellular system models are targeted.

In this correspondence, joint (cooperative) decoding at the base stations combined with collaborative transmission (relaying) is investigated as a means to improve the uplink throughput of current cellular systems over fading channels. Intracell orthogonal medium access control (e.g., TDMA, FDMA, or orthogonal CDMA) and Decode-and-Forward relaying by either a mobile terminal or a fixed relay are assumed. Moreover, the cellular system is modeled according to a simplified framework introduced by Wyner. The per-cell achievable ergodic throughput is calculated for different system configurations and then characterized in the low-power (wideband) regime in terms of minimum energy per bit required for reliable communication and slope of the spectral efficiency. The analysis allows to clearly assess the relative merits of both cooperation among base stations and at the terminal level within the considered model.

In this contribution we present new achievable rates, for the non-fading uplink channel of a cellular network, with joint cell-site processing, where unlike previous results, the error-free backhaul network has finite capacity per-cell. Namely, the cell-sites are linked to the central joint processor via lossless links with finite capacity. The cellular network is modeled by the circular Wyner model, which yields closed form expressions for the achievable rates. For this idealistic model, we present achievable rates for cell-sites that use compress-and forward scheme, combined with local decoding, and inter-cell time-sharing. These rates are then demonstrated to be rather close to the optimal unlimited backhaul joint processing rates, already for modest backhaul capacities, supporting the potential gain offered by the joint cell-site processing approach.

In this paper the benefits provided by multi-cell processing of signals transmitted by mobile terminals which are received via dedicated relay terminals (RTs) are assessed. Unlike previous works, each RT is assumed here to be capable of full-duplex operation and receives the transmission of adjacent relay terminals. Focusing on intra-cell TDMA and non-fading channels, a simplified uplink cellular model introduced by Wyner is considered. This framework facilitates analytical derivation of the per-cell sum-rate of multi-cell and conventional single-cell receivers. In particular, the analysis is based on the observation that the signal received at the base stations can be interpreted as the outcome of a two-dimensional linear time invariant system. Numerical results are provided as well in order to provide further insight into the performance benefits of multi-cell processing with relaying.

In this paper, we consider downlink throughput performances of multiuser orthogonal frequency division multiplexing (multiuser OFDM) with reduced channel information feedback schemes. Specifically, two types of reduced feedback schemes, namely, 1-bit per sub-carrier and selective feedback scheme are considered and compared with each other in terms of average network throughput. For the latter, since the exact analysis is complicated, we resort to an approximate analysis. Simulations results will also be provided to verify the approximate analysis. Since the strict throughput comparison for given number of feedback bits per user is quite difficult, rather we compare their general behaviors in various system configurations with different system parameters, which can give us an insight into practical system design with those reduced feedback schemes.

Achip-interleavedrandomly spread direct-sequence code-division multiple-access (DS-CDMA) scheme is considered, employed in two variants of Wyner's infinite linear cell-array model with flat fading. Focusing on the asymptotic setup in which both the number of users per cell and the processing gain go to infinity, while their ratio (the “cell load”) goes to some finite constant, the spectral efficiencies of the optimum and linear minimum mean-squared error (MMSE)joint multicell receiversare investigated. A dramatic performance enhancement as compared tosingle-cell-site processing is demonstrated. The asymptotic behavior of the two receivers in extreme signal-to-noise ratio (SNR) regimes and in a high cell-load regime are analyzed as well. The impact of chip interleaving versus symbol interleaving is also investigated. Chip-level interleaving is found beneficial in several cases of interests, and is conjectured to be beneficial in general.

The sum-rate capacity of a cellular system model is analyzed, considering the uplink and downlink channels, while addressing both nonfading and flat-fading channels. The focus is on a simple Wyner-like multicell model, where the system cells are arranged on a circle, and the cell sites are located at the boundaries of the cells. For the uplink channel, analytical expressions of the sum-rate capacities are derived for intra-cell time-division multiple-access (TDMA) scheduling, and a “wideband” (WB) scheme (where all users are active simultaneously utilizing all bandwidths for coding). Assuming individual equal per-cell power constraints, and using the Lagrangian uplink–downlink duality principle, an analytical expression for the sum-rate capacity of the downlink channel is derived for nonfading channels, and shown to coincide with the corresponding uplink result. Introducing flat-fading, lower and upper bounds on the average per-cell ergodic sum-rate capacity are derived. The bounds exhibit an$O(\log _{e} K)$multiuser diversity factor for a number of users per cell$K\gg 1$, in addition to the array diversity gain. Joint multicell processing is shown to eliminate out-of-cell interference, which is traditionally considered to be a limiting factor in high-rate reliable communications.

Cooperation between base stations and collaborative transmission between mobile terminals are two technologies currently under study as promising paradigms for next generation communications systems. In this paper, we provide a first look to the interplay between these two approaches by studying the per-cell achievable sum-rate (throughput) of different cooperative protocols under a simplified model for the uplink of a TDMA cellular system. The analysis is limited to non-regenerative (amplify-and-forward) cooperation schemes between terminals for their'simplicity and appeal to a practical implementation. A closed form expression for the (asymptotic) achievable rate of multicell processing combined with amplify-and-forward collaboration at the terminals is derived for an AWGN (i.e., no fading) scenario. Moreover, the impact of fading is investigated numerically, allowing to draw some conclusions on the impact of multicell diversity (or macrodiversity) on the performance of collaborative schemes among the terminals. In particular, we show that while AF cooperation is generally advantageous for single cell processing (i.e., with no collaboration between base stations), its benefits when combined with multicell processing are limited to the regime of low to moderate transmission rates.

For a multiple-input single-output (MISO) downlink channel with M transmit antennas, it has been recently proved that zero-forcing beamforming (ZFBF) to a subset of (at most) M "semi-orthogonal" users is optimal in terms of the sum-rate, asymptotically with the number of users. However, determining the subset of users for transmission is a complex optimization problem. Adopting the ZFBF scheme in a cooperative multi-cell scenario renders the selection process even more difficult since more users are involved. In this paper, we consider a multi-cell cooperative ZFBF scheme combined with a simple sub-optimal users selection procedure for the Wyner downlink channel setup. According to this sub-optimal procedure, the user with the "best" local channel is selected for transmission in each cell. It is shown that under an overall power constraint, a distributed multi-cell ZFBF to this sub-optimal subset of users achieves the same sum-rate growth rate as an optimal scheme deploying joint multi-cell dirty-paper coding (DPC) techniques, asymptotically with the number of users per cell. Moreover, the overall power constraint is shown to ensure in probability, equal per-cell power constraints when the number of users per-cell increases.

The sum-capacity of the multi-antenna Gaussian broadcast channel is known to be achieved by Dirty Paper Coding techniques, that require full channel state information at the base station. It has been recently shown that a sum-rate having the same scaling law of the sum-capacity with respect to the number of users n for a fixed signal to noise ratio (i.e., M log log n where M is the number of transmitting antennas) can be achieved by using reduced feedback (or equivalently reduced channel state information at the transmitter). In particular, it has been proved that n real and n integer numbers are enough to guarantee the optimal scaling law. In this paper, the optimal scaling law of the sum-rate is shown to be achievable with an even smaller amount of feedback and, more precisely, with 1) n log2(M + 1) bits, if a deterministic feedback scheme is employed; 2) an average number of feedback bits that scales as M log2M log n with the number of users n, if a selective (random) feedback scheme is employed.

We consider a chip-interleaved randomly spread DS-CDMA scheme employed in Wyner's infinite linear cell-array model with flat fading. Focusing on the asymptotic setup, the per-cell spectral efficiencies of the optimum and linear MMSE joint multicell receivers are considered. Performance enhancement as compared to single-cell-site processing is demonstrated. The asymptotic behavior of the two receivers in extreme SNR regimes and in a high cell-load setup is analyzed as well. The impact of chip interleaving vs. symbol interleaving is also considered.

Shannon-theoretic limits on the achievable throughput for a simple infinite cellular multiple-access channel (MAC) model (Wyner 1994) in the presence of fading are presented. In this model, which is modified to account for flat fading, the received signal, at a given cell-site's antenna, is the sum of the faded signals transmitted from all users within that cell plus an attenuation factor /spl alpha//spl isin/[0,1] times the sum of the faded signals received from the adjacent cells, accompanied by Gaussian additive noise. This model serves as a tractable model providing considerable insight into complex and analytically intractable real-world cellular communications. Both linear and planar cellular arrays are considered with exactly K active users in each cell. We assume a hyper-receiver, jointly decoding all of the users, incorporating the received signals from all of the active cell-sites. The hyper-receiver is assumed to be aware of the codebooks and realizations of the fading processes of all the users in the system. In this work we consider the intracell time-division multiple-access (TDMA) and the wideband (WB) protocols. We focus on the maximum reliably transmitted equal rate. Bounds to this rate are found for the intracell TDMA protocol by incorporating information-theoretic inequalities and the Chebyshev-Markov moment theory as applied to the limiting distribution of the eigenvalues of a quadratic form of tridiagonal random matrices. We demonstrate our results for the special case where the amplitudes of the fading coefficients are drawn from a Rayleigh distribution, i.e., Rayleigh fading. For this special case, we observe the rather surprising result that fading may increase the maximum equal rate, for a certain range of /spl alpha/ as compared to the nonfaded case. In this setting, the WB strategy, which achieves the maximum reliable equal rate of the model, is proved to be superior to the TDMA scheme. An upper bound to the maximum equal rate of the WB scheme is also obtained. This bound is asymptotically tight when the number of users is large (K/spl Gt/1). The asymptotic bound shows that the maximum equal rate of the WB scheme in the presence of fading is higher than the rate which corresponds to the nonfaded case for any intercell interference factor /spl alpha//spl isin/[0,1] signal-to-noise ratio (SNR) values. This result is found to be independent of the statistics of the fading coefficients.

Shannon-theoretic limits on the achievable throughput for a simple cellular multiple-access system (referred to as Wyner's (1994) model) in the presence of fading are presented. In this model, which is modified to account for flat fading, the received signal at a given cell-site is the sum of the faded signals transmitted from all users within that cell, plus an attenuation factor /spl alpha/ /spl isin/ [0,1] times the sum of the faded signals received from the adjacent cells, accompanied with an additive Gaussian noise. Although this simple model is scarcely realistic, it serves as a simple tractable model which provides considerable insight into complex and intractable real-world cellular communication systems. We assume a hyper (super)-receiver, jointly decoding all the users, using the received signals from all the active cell-sites. The hyper-receiver is assumed to be aware of the codebooks and realizations of the fading processes of each user. We consider the intra-cell time division multiple access (TDMA) protocol which is known to be equivalent to the optimal protocol under the average power constraint in the absence of fading. We are interested in the maximum reliably transmitted equal rate (system throughput per user). Bounds on this rate are found by incorporating information-theoretic inequalities and the Tchebycheff-Markov moment bounding technique. We observe the rather surprising result that flat fading (Rayleigh) may increase the maximum equal rate for a certain range of /spl alpha/ and signal to noise ratio (SNR) in comparison to the non-faded case.