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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
Arithmetic and communication complexity of preconditioning methods
Katholieke Universiteit Nijmegen, 27 september 1995
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
Page 1 of 8