Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 141 for “"communication complexity"”.

  1. Multiparty Communication Complexity

    Communication complexity is an area of complexity theory that studies an abstract model of computation called a communication protocol. In a k-player communication protocol, an input to a known function is partitioned into k pieces of n bits each, and each piece is assigned to one of the players in …

    toronto-retro Repository record for Multiparty Communication Complexity (opens in a new tab)

  2. Communication Complexity of Remote State Preparation

    … cannot be sent with less than n bits of communication in LOCC protocols even in the presence of prior entanglement. This is an interesting result which will be used in the rest of this thesis. Quantum teleportation uses prior entanglement and classical communication to send an unknown …

    waterloo Repository record for Communication Complexity of Remote State Preparation (opens in a new tab)

  3. Improved XOR Lemmas for Communication Complexity

    We give communication lower bounds for computing the $n$-fold XOR of a given Boolean function $f$, denoted $f^{\oplus n}(x,y) := f(x_1,y_1)\oplus\ldots\oplus f(x_n,y_n)$, in both the deterministic and the randomized setting. In addition, we also give deterministic communication lower bounds on …

    washington Repository record for Improved XOR Lemmas for Communication Complexity (opens in a new tab)

  4. Lower bound methods for multiparty communication complexity

    Multiparty communication complexity is a measure of the amount of communication required to compute a function whose input is distributed among multiple parties. Proving lower bounds in the “Number on the Forehead” model of Chandra, Furst, and Lipton has been quite difficult, but results are of …

    texas Repository record for Lower bound methods for multiparty communication complexity (opens in a new tab)

  5. Studies in Communication Complexity and Semidefinite Programs

    … part concerns strong direct product results in communication complexity. In the first part, we study fast parallel approximation algorithms for certain classes of semidefinite programs. In Chapter 3, we present a fast parallel approximation algorithm for positive semidefinite programs. In …

    nus Repository record for Studies in Communication Complexity and Semidefinite Programs (opens in a new tab) Download file for Studies in Communication Complexity and Semidefinite Programs (opens in a new tab)

  6. Computational and communication complexity of geometric problems

    … in this model. We prove lower bounds on the communication complexity of the problems in the fixed-link model and present approximation algorithms for them. We prove lower bounds on the number of expected bits required for any randomized algorithm in the fixed-link model with $n$ nodes to …

    uvic Repository record for Computational and communication complexity of geometric problems (opens in a new tab)

  7. Improvements in communication complexity using quantum entanglement

    … been known to provide speed-ups in computational complexity in many algorithms. The impact of these resources in communication, however, has not attracted much attention. We investigate the impact of quantum entanglement on communication complexity. We provide a positive result, by presenting a …

    tamu Repository record for Improvements in communication complexity using quantum entanglement (opens in a new tab)

  8. PROBLEMS IN QUANTUM TAMPER RESILIENT CRYPTOGRAPHY AND QUANTUM COMMUNICATION COMPLEXITY

    … thesis, we study a problem related to quantum communication complexity. In particular, we disprove the quantum log-approximate-rank conjecture of Lee and Shraibman [LS08], which states that for a total function f, the log-approximate-rank of the communication matrix corresponding to f and …

    nus Repository record for PROBLEMS IN QUANTUM TAMPER RESILIENT CRYPTOGRAPHY AND QUANTUM COMMUNICATION COMPLEXITY (opens in a new tab) Download file for PROBLEMS IN QUANTUM TAMPER RESILIENT CRYPTOGRAPHY AND QUANTUM COMMUNICATION COMPLEXITY (opens in a new tab)

  9. Topics in analysis of Boolean functions with applications to communication complexity

    … these relationships leads to applications in communication complexity. The primary application we consider is to the log-rank conjecture for XOR functions — a special case of the log-rank conjecture, one of the most central open problems in communication complexity. Despite being introduced …

    texas Repository record for Topics in analysis of Boolean functions with applications to communication complexity (opens in a new tab)

  10. Lower bounds in communication complexity and learning theory via analytic methods

    … this research objective in the contexts of communication complexity and computational learning theory. In the former case, one seeks to understand which distributed computations require a significant amount of communication among the parties involved. In the latter case, one aims to …

    texas Repository record for Lower bounds in communication complexity and learning theory via analytic methods (opens in a new tab)

  11. The Communication Complexity of Fault-Tolerant Distributed Computation of Aggregate Functions

    Multi-party communication complexity involves distributed computation of a function over inputs held by multiple distributed players. A key focus of distributed computing research, since the very beginning, has been to tolerate failures. It is thus natural to ask ``{\em If we want to compute a …

    nus Repository record for The Communication Complexity of Fault-Tolerant Distributed Computation of Aggregate Functions (opens in a new tab) Download file for The Communication Complexity of Fault-Tolerant Distributed Computation of Aggregate Functions (opens in a new tab)

  12. Distributed broadcast and minimum spanning tree algorithms with low communication complexity

    … size over links available on a predetermined communication network. In this thesis, we consider the problems of broadcast and minimum spanning tree construction in a distributed setting. These problems are of fundamental importance. Efficient solutions for these problems can lead to …

    uvic Repository record for Distributed broadcast and minimum spanning tree algorithms with low communication complexity (opens in a new tab)

  13. Communication, complexity and empire: The systemic thought of Harold Adams Innis.

    … on Canadian economic history and history of communication technologies are still highly regarded, still widely cited and still viewed as providing an exceptionally powerful framework for interpreting the histories of societies past and present. The problem, however, is that scholars remain …

    ottawa-retro Repository record for Communication, complexity and empire: The systemic thought of Harold Adams Innis. (opens in a new tab)

  14. On the Streaming and Communication Complexity for Interval and Graph Problems

    … problems in the streaming and one-way<br/>communication complexity settings.<br/>In the Interval Selection problem we are given a set of intervals, and asked for a largest pair<br/>wise non-overlapping subset. Previous work gave tight results for the one-pass insertion-only<br/>streaming …

    bristol Repository record for On the Streaming and Communication Complexity for Interval and Graph Problems (opens in a new tab) Download PDF for On the Streaming and Communication Complexity for Interval and Graph Problems (opens in a new tab)

  15. Assessing Intentional Communication in Typically Developing Infants Using the Communication Complexity Scale

    The Communication Complexity Scale (CCS; Brady, Fleming, Thiemann-Borque, Olswang, Dowden, Saunders, & Marquis, 2012) is a criterion-referenced assessment of early, primarily pre-linguistic, communication signals. It produces an expressive communication summary score, based on the most …

    washington Repository record for Assessing Intentional Communication in Typically Developing Infants Using the Communication Complexity Scale (opens in a new tab)

  16. Assessing Intentional Communication in Typically Developing Infants Using the Communication Complexity Scale

    The Communication Complexity Scale (CCS; Brady, Fleming, Thiemann-Borque, Olswang, Dowden, Saunders, & Marquis, 2012) is a criterion-referenced assessment of early, primarily pre-linguistic, communication signals. It produces an expressive communication summary score, based on the most …

    washington Repository record for Assessing Intentional Communication in Typically Developing Infants Using the Communication Complexity Scale (opens in a new tab)

  17. Live coding the Communication Complexity Scale: Validation of a clinically relevant observation tool

    … scoring of the observational rating tool, the Communication Complexity Scale (CCS), was examined through three participant variables and one assessment variable: communication level of the participant, age of the participant, severity of autism of the participant, and assessment task function …

    ku Repository record for Live coding the Communication Complexity Scale: Validation of a clinically relevant observation tool (opens in a new tab)

  18. The Communication Complexity of Distributed Computing and a Parallel Algorithm for Polynomial Roots

    … we begin with a discussion of the minimum communication requirements in some distributed networks. The main result is a general technique for determining lower bounds on the communication complexity of problems on various distributed computer networks. This general technique is derived by …

    uiuc Repository record for The Communication Complexity of Distributed Computing and a Parallel Algorithm for Polynomial Roots (opens in a new tab)

  19. EFFECTS OF COMMUNICATION COMPLEXITY ON ANALOGUE CLIENTS IN A VIDEO CANCER GENETIC COUNSELING SESSION

    Objective: Communication of information plays a central role in genetic counseling. There have been few direct comparisons of differing communication approaches. This research study aimed to experimentally manipulate communication of genetic information and to describe how the complexity of …

    jhu Repository record for EFFECTS OF COMMUNICATION COMPLEXITY ON ANALOGUE CLIENTS IN A VIDEO CANCER GENETIC COUNSELING SESSION (opens in a new tab)

Page 1 of 8