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 37 for “"Communication complexity"”.
-
Communication complexity of permutation-invariant functions
… by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of "permutation-invariant" functions. A partial function f : {0, 1}n x {0, 1}n --> {0, 1, ?} is permutation-invariant if for every bijection [pi]: {1,..., n} --> {1,.. ., n} and …
-
Fine-grained complexity meets communication complexity
Fine-grained complexity aims to understand the exact exponent of the running time of fundamental problems in P. Basing on several important conjectures such as Strong Exponential Time Hypothesis (SETH), All-Pair Shortest Path Conjecture, and the 3-Sum Conjecture, tight conditional lower bounds are …
-
Communication complexity of distributed shortest path algorithms
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1979.
-
Communication complexity of some problems in distributed computation
Thesis (Sc. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1989.
-
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 …
-
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 …
-
DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY
… direct product and composition theorems in query complexity, communication complexity and non-local games, and show applications of these results in device-independent cryptography. The first part of the thesis deals with direct product and composition theorems. Our first result in this part is a …
-
Improving Performance of Consensus Protocols
… important challenges include improving the round complexity, the communication complexity of the protocol and tolerating strong adversaries. For round complexity, under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant …
-
Distributed computation in wireless and dynamic networks
… round to round, as long as in each round the communication graph is connected. We show that even in this weak model, global computation is still possible, and any function of the nodes' initial inputs can be computed efficiently. Also, using tools from the field of epistemic logic, we analyze …
-
The loudest one wins : efficient communication in theoretical wireless networks
… that solves the leader election problem in two communication rounds using power control, with high probability. Previously, it was known that [Omega](log n) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network. We explore tradeoffs between …
-
Distributed Training with Heterogeneous Data: Bridging Median- and Mean-Based Algorithms
… with majority vote, an effective approach for communication reduction via 1-bit compression on the local gradients, and medianSGD, an algorithm recently proposed to ensure robustness against Byzantine workers. The convergence analyses for these algorithms critically rely on the assumption that …
-
Pattern matching encryption, strategic equivalence of range voting and approval voting, and statistical robustness of voting rules
… queries, based on suffix trees. Storage and communication complexity are comparable to those for (unencrypted) suffix trees. The construction is based only on symmetric-key primitives, so it is practical. 2. Strategic equivalence of range voting and approval voting: We study strategic voting …
-
Information tracking and sharing in organic photovoltaic panel manufacturing
… boards were developed to alleviate this communication complexity. One Kanban (card style) board was implemented to keep track of production information, and another Kaizen (continuous improvement) board was established to keep track of all the continuous activities on the shop floor. …
-
Seedless Extractors
… theory with deep connections to cryptography, complexity theory, and combinatorics. As it is impossible to construct a single extractor that works for all weak sources of randomness, research on extractors has split into two complementary settings: (1) the seeded setting, where the extractor is …
-
Some hardness escalation results in computational complexity theory
… new hardness escalation results in computational complexity theory; a phenomenon where hardness results against seemingly weak models of computation for any problem can be lifted, in a black box manner, to much stronger models of computation by considering a simple gadget composed version of the …
-
Efficient and private distance approximation in the communication and streaming models
… models - the streaming model and the two-party communication model. In the streaming model, a massive data stream is presented in an arbitrary order to a randomized algorithm that tries to approximate certain statistics of tile data with only a few (usually one) passes over the data. For …
-
Secure computation on untrusted platforms
… many statements with roughly the same (small) communication complexity as is required to prove a single statement. The soundness guarantee is that the verifier cannot be fooled even by malicious provers that can, in a very limited sense, collude in their messages to the verifier. The latter …
-
Hierarchical Game Theory based Control for Large Scale Multi-Agent Systems: A Hybrid Reinforcement Learning Approach
… critical due to the challenges of scalability, communication complexity, and computational intractability. Traditional control approaches face the curse of dimensionality as the number of interacting agents increases, making them unsuitable for real-time implementation in dense environments. To …
Page 1 of 2