skip to main content


Title: A Wringing-Based Proof of a Second-Order Converse for the Multiple-Access Channel under Maximal Error Probability
The second-order converse bound of multiple access channels is an intriguing problem in information theory. In this work, in the setting of the two-user discrete memoryless multiple access channel (DM-MAC) under the maximal error probability criterion, we investigate the gap between the best achievable rates and the asymptotic capacity region. With “wringing techniques” and meta-converse arguments, we show that gap at blocklength n is upper bounded by O(1/√n) .  more » « less
Award ID(s):
1908725
NSF-PAR ID:
10296643
Author(s) / Creator(s):
;
Date Published:
Journal Name:
2021 IEEE International Symposium on Information Theory (ISIT)
Page Range / eLocation ID:
2220 to 2225
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. In recent years, the popularity of AI-enabled conversational agents or chatbots has risen as an alternative to traditional online surveys to elicit information from people. However, there is a gap in using single-agent chatbots to converse and gather multi-faceted information across a wide variety of topics. Prior works suggest that single-agent chatbots struggle to understand user intentions and interpret human language during a multi-faceted conversation. In this work, we investigated how multi-agent chatbot systems can be utilized to conduct a multi-faceted conversation across multiple domains. To that end, we conducted a Wizard of Oz study to investigate the design of a multi-agent chatbot for gathering public input across multiple high-level domains and their associated topics. Next, we designed, developed, and evaluated CommunityBots - a multi-agent chatbot platform where each chatbot handles a different domain individually. To manage conversation across multiple topics and chatbots, we proposed a novel Conversation and Topic Management (CTM) mechanism that handles topic-switching and chatbot-switching based on user responses and intentions. We conducted a between-subject study comparing CommunityBots to a single-agent chatbot baseline with 96 crowd workers. The results from our evaluation demonstrate that CommunityBots participants were significantly more engaged, provided higher quality responses, and experienced fewer conversation interruptions while conversing with multiple different chatbots in the same session. We also found that the visual cues integrated with the interface helped the participants better understand the functionalities of the CTM mechanism, which enabled them to perceive changes in textual conversation, leading to better user satisfaction. Based on the empirical insights from our study, we discuss future research avenues for multi-agent chatbot design and its application for rich information elicitation.

     
    more » « less
  2. This study examines the relationship between households' access to critical facilities day-to-day and during weather-related extreme events. Despite a robust understanding of both day-to-day access and access during disasters, the interplay between the two remains unclear. To bridge this knowledge gap, we propose a novel empirical approach, using a Texas statewide household survey (N = 810). The survey evaluates day-to-day and past events access, exploring the experiences of respondents during multiple recent disasters, rather than focusing on a specific hazard. Using correlation analysis, we examined various access-related factors such as day-to-day trip duration, alternative trip duration, and loss of access during past events. Additionally, we evaluated the association between access-related factors and sociodemographic characteristics such as income, ethnicity, and urban status. The results indicate: (1) daily trip duration to critical facilities is associated with disrupted access during storm events, and (2) disparities persist during both day-to-day times and during extreme events. These results bring new insights to the existing body of knowledge on day-to-day access and access during disasters. The findings provide scientifically grounded evidence to city managers and planners, emphasizing the need for equitable distribution of facilities to enhance access to essential facilities both in daily life and during extreme weather-related events. 
    more » « less
  3. Abstract Objectives

    Food and water insecurity have both been demonstrated as acute and chronic stressors and undermine human health and development. A basic untested proposition is that they chronically coexist, and that household water insecurity is a fundamental driver of household food insecurity.

    Methods

    We provide a preliminary assessment of their association using cross‐sectional data from 27 sites with highly diverse forms of water insecurity in 21 low‐ and middle‐income countries across Africa, Asia, the Middle East, and the Americas (N = 6691 households). Household food insecurity and its subdomains (food quantity, food quality, and anxiety around food) were estimated using the Household Food Insecurity Access Scale; water insecurity and subdomains (quantity, quality, and opportunity costs) were estimated based on similar self‐reported data.

    Results

    In multilevel generalized linear mixed‐effect modeling (GLMM), composite water insecurity scores were associated with higher scores for all subdomains of food insecurity. Rural households were better buffered against water insecurity effects on food quantity and urban ones for food quality. Similarly, higher scores for all subdomains of water insecurity were associated with greater household food insecurity.

    Conclusions

    Considering the diversity of sites included in the modeling, the patterning supports a basic theory: household water insecurity chronically coexists with household food insecurity. Water insecurity is a more plausible driver of food insecurity than the converse. These findings directly challenge development practices in which household food security interventions are often enacted discretely from water security ones.

     
    more » « less
  4. Polyanskiy [1] proposed a framework for the MAC problem with a large number of users, where users employ a common codebook in the finite blocklength regime. In this work, we extend [1] to the case when the number of active users is random and there is also a delay constraint. We first define a random-access channel and derive the general converse bound. Our bound captures the basic tradeoff between the required energy and the delay constraint. Then we propose an achievable bound for block transmission. In this case, all packets are transmitted in the second half of the block to avoid interference. We then study treating interference as noise (TIN) with both single user and multiple users. Last, we derive an achievable bound for the packet splitting model, which allows users to split each packet into two parts with different blocklengths. Our numerical results indicate that, when the delay is large, TIN is effective; on the other hand, packet splitting outperforms as the delay decreases. 
    more » « less
  5. A bstract According to the AdS/CFT correspondence , the geometries of certain spacetimes are fully determined by quantum states that live on their boundaries — indeed, by the von Neumann entropies of portions of those boundary states. This work investigates to what extent the geometries can be reconstructed from the entropies in polynomial time . Bouland, Fefferman, and Vazirani (2019) argued that the AdS/CFT map can be exponentially complex if one wants to reconstruct regions such as the interiors of black holes. Our main result provides a sort of converse: we show that, in the special case of a single 1D boundary divided into N “atomic regions”, if the input data consists of a list of entropies of contiguous boundary regions, and if the entropies satisfy a single inequality called Strong Subadditivity, then we can construct a graph model for the bulk in linear time. Moreover, the bulk graph is planar, it has O ( N 2 ) vertices (the information-theoretic minimum), and it’s “universal”, with only the edge weights depending on the specific entropies in question. From a combinatorial perspective, our problem boils down to an “inverse” of the famous min-cut problem: rather than being given a graph and asked to find a min-cut, here we’re given the values of min-cuts separating various sets of vertices, and need to find a weighted undirected graph consistent with those values. Our solution to this problem relies on the notion of a “bulkless” graph, which might be of independent interest for AdS/CFT. We also make initial progress on the case of multiple 1D boundaries — where the boundaries could be connected via wormholes — including an upper bound of O ( N 4 ) vertices whenever an embeddable bulk graph exists (thus putting the problem into the complexity class NP). 
    more » « less