Relevant bibliographies by topics / Round and communication complexity

Academic literature on the topic 'Round and communication complexity'

Author: Grafiati
Published: 10 December 2022
Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Round and communication complexity.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Round and communication complexity"

1

Kremer, I., N. Nisan, and D. Ron. "On Randomized One-round Communication Complexity." Computational Complexity 8, no. 1 (June 1, 1999): 21–49. http://dx.doi.org/10.1007/s000370050018.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Kremer, Ilan, Noam Nisan, and Dana Ron. "Errata for: "On randomized one-round communication complexity"." Computational Complexity 10, no. 4 (December 1, 2001): 314–15. http://dx.doi.org/10.1007/s000370100003.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Pandurangan, Gopal, Peter Robinson, and Michele Scquizzato. "On the Distributed Complexity of Large-Scale Graph Computations." ACM Transactions on Parallel Computing 8, no. 2 (June 30, 2021): 1–28. http://dx.doi.org/10.1145/3460900.

Full text
Abstract:
Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main contribution is the General Lower Bound Theorem , a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. This result is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic, and this theorem can be used in a “cookbook” fashion to show distributed lower bounds for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely, PageRank computation and triangle enumeration . These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input. We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds; these algorithms exhibit a round complexity that scales superlinearly in k , improving significantly over previous results [Klauck et al., SODA 2015]. Specifically, we show the following results: PageRank: We show a lower bound of Ὼ(n/k 2 ) rounds and present a distributed algorithm that computes an approximation of the PageRank of all the nodes of a graph in Õ(n/k 2 ) rounds. Triangle enumeration: We show that there exist graphs with m edges where any distributed algorithm requires Ὼ(m/k 5/3 ) rounds. This result also implies the first non-trivial lower bound of Ὼ(n 1/3 ) rounds for the congested clique model, which is tight up to logarithmic factors. We then present a distributed algorithm that enumerates all the triangles of a graph in Õ(m/k 5/3 + n/k 4/3 ) rounds.
APA, Harvard, Vancouver, ISO, and other styles
4

Zhao, Bo, Zhihong Chen, Hai Lin, and XiangMin Ji. "A Constant Round Write-Only ORAM." Applied Sciences 10, no. 15 (August 3, 2020): 5366. http://dx.doi.org/10.3390/app10155366.

Full text
Abstract:
The write-only oblivious RAM (ORAM) is proposed to efficiently protect the privacy of applications such as cloud storage synchronization and encrypted hidden volumes. For N blocks with size B = Ω(log2N), the most efficient write-only ORAM, DetWoORAM, achieves O(B) communication complexity with O(logN) rounds per logical write. We propose a two-level write-only ORAM and achieve O(B) communication complexity with O(1) rounds. Similar to the traditional bucket-based ORAM schemes, we set a rate for the write operation to further reduce the communication complexity. The top-level stores data blocks in a flat array and the write pattern is protected by writing blocks uniformly at random. The second level employs a binary tree to store the position map of data blocks. To avoid recursive storage, a static position map for blocks in the second level is used. Both the analysis and experiments show that, besides the achieved low communication complexity and rounds, the stash sizes in the top level and the second level are bounded to O(B) and ω(B), respectively.
APA, Harvard, Vancouver, ISO, and other styles
5

Apon, Daniel, Jonathan Katz, and Alex J. Malozemoff. "One-round multi-party communication complexity of distinguishing sums." Theoretical Computer Science 501 (August 2013): 101–8. http://dx.doi.org/10.1016/j.tcs.2013.07.026.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

TSE, SAVIO S. H., and FRANCIS C. M. LAU. "ON THE COMPLEXITY OF SOME ADAPTIVE POLLING ALGORITHMS IN GENERAL NETWORKS." International Journal of Foundations of Computer Science 10, no. 02 (June 1999): 211–23. http://dx.doi.org/10.1142/s0129054199000150.

Full text
Abstract:
We study the problem of adaptive polling in undirected general networks. Polling, also known as broadcast-confirm, consists a propagation round and a feedback round. In adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths in order to adapt to traffic and fault situations. We study three adaptive polling algorithms and analyze their worst-case communication bit complexities in the propagation round. Then, we prove a lower bound on the worst-case communication bit complexity of Ω(e+n log n) in the propagation round for all algorithms of the same kind as the three algorithms we study, where n is the number of nodes, and e the number of edges. We conclude that the cost introduced into the network due to the running of an adaptive polling algorithm is mild.
APA, Harvard, Vancouver, ISO, and other styles
7

Wagh, Sameer. "Pika: Secure Computation using Function Secret Sharing over Rings." Proceedings on Privacy Enhancing Technologies 2022, no. 4 (October 2022): 351–77. http://dx.doi.org/10.56553/popets-2022-0113.

Full text
Abstract:
Machine learning algorithms crucially depend on non-linear mathematical functions such as division (for normalization), exponentiation (for softmax and sigmoid), tanh (as an activation function), logarithm (for crossentropy loss), and square root (for back-propagation of normalization layers). However, when machine learning is performed over secure computation, these protocols incur a large communication overhead and high round complexity. In this work, we propose new multi-party computation (MPC) protocols for such functions. Our protocols achieve constant round complexity (3 for semi-honest, 4 for malicious), an order of magnitude lower communication (54 − 121× lower than prior art), and high concrete efficiency (2−1163× faster runtime). We rely on recent advances in function secret sharing (FSS) to construct these protocols. Our contributions can be summarized as follows: (1) A constant round protocol to securely evaluate nonlinear functions such as division, exponentiation, logarithm, and tanh (in comparison to prior art which uses round complexity proportional to the rounds of iterative methods/required precision) with high accuracy. This construction largely follows prior work in look-up style secure computation. (2) Our main contribution is the extension of the above protocol to be secure in the presence of malicious adversaries in the honest majority setting. We provide a malicious sketching protocol for FSS schemes that works over rings and in order to prove its security, we extend (and prove) a corresponding form of SchwartzZippel lemma over rings. This is the first such extension of the lemma and it can be of independent interest in other domains of secure computation. (3) We implement our protocol and showcase order of magnitude improvements in runtime and communication. Given the low round complexity and substantially lower communication, our protocols achieve even better performance over network constrained environments such as WAN. Finally, we showcase how such functions can lead to scalability in machine learning. Note that techniques presented are applicable beyond the application of machine learning as the protocols effectively present an efficient 1-out-of-N oblivious transfer or an efficient private information retrieval protocol.
APA, Harvard, Vancouver, ISO, and other styles
8

Zhang, Kai, Xuejia Lai, Lei Wang, Jie Guan, Bin Hu, Senpeng Wang, and Tairong Shi. "Related-Key Multiple Impossible Differential Cryptanalysis on Full-Round LiCi-2 Designed for IoT." Security and Communication Networks 2022 (May 25, 2022): 1–11. http://dx.doi.org/10.1155/2022/3611840.

Full text
Abstract:
LiCi-2 is an ultralightweight block cipher designed for constrained IoT devices. It is a successor of LiCi and has even better performance in both software and hardware implementation. In this paper, based on the idea of related-key multiple impossible differential cryptanalysis, a key recovery attack on full-round LiCi-2 is proposed. First, an interesting property is revealed that, with a single bit difference in the related key, a 10-round differential character with probability of 1 exists on LiCi-2. With an automatic approach, the boundaries of impossible differential distinguishers in terms of single-key setting and related-key setting are explored. Under our construction method, the longest length is 8 rounds for single-key setting and 18 rounds for related-key setting. Finally, based on these 18-round distinguishers, a 25-round key recovery attack is proposed with adding 3 rounds before and 4 rounds after the distinguisher. Our attack needs one related key. The time complexity for our attack is O(2123.44), the memory complexity is O(294), and the data complexity is O(260.68). As far as we know, no full-round attack has previously been reported on LiCi-2.
APA, Harvard, Vancouver, ISO, and other styles
9

Tse, Savio S. H. "Belated Analyses of Three Credit-Based Adaptive Polling Algorithms." International Journal of Foundations of Computer Science 27, no. 05 (August 2016): 579–94. http://dx.doi.org/10.1142/s0129054116500179.

Full text
Abstract:
We study the problem of credit-based adaptive polling in undirected arbitrary point-to-point asynchronous networks. Polling consists of two rounds, namely propagation (broadcast) and feedback (confirmation, response) rounds. By adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths back to the initiator — a specific node who initiates the polling algorithm. The freedom in the feedback round relies on the use of credits in the propagation round. We re-visit three existing algorithms and analyse their average case communication bit complexities incurred by the credits in the propagation round, and these analyses match with the numerical results. We also give an optimal lower bound on the worst case bit message complexity for the case when the number of nodes in the network is unknown.
APA, Harvard, Vancouver, ISO, and other styles
10

Magniez, Frédéric, and Ashwin Nayak. "Quantum Distributed Complexity of Set Disjointness on a Line." ACM Transactions on Computation Theory 14, no. 1 (March 31, 2022): 1–22. http://dx.doi.org/10.1145/3512751.

Full text
Abstract:
Given \( x,y\in \lbrace 0,1\rbrace ^n \) , Set Disjointness consists in deciding whether \( x_i=y_i=1 \) for some index \( i \in [n] \) . We study the problem of computing this function in a distributed computing scenario in which the inputs \( x \) and \( y \) are given to the processors at the two extremities of a path of length \( d \) . Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging \( \operatorname{O}(\log n) \) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from \( 1/2 \) . We call this problem “Set Disjointness on a Line”. Set Disjointness on a Line was introduced by Le Gall and Magniez [ 14 ] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of \( \operatorname{O}(\log n) \) qubits. In this work, we prove an unconditional lower bound of \( \widetilde{\Omega }\big (\sqrt [3]{n d^2}+\sqrt {n} \, \big) \) rounds for Set Disjointness on a Line with \( d + 1 \) processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of \( \widetilde{\Omega } \big (\sqrt [3]{n\delta ^2}+\sqrt {n} \, \big) \) on the number of rounds required for computing the diameter \( \delta \) of any \( n \) -node network with quantum messages of size \( \operatorname{O}(\log n) \) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function \( f \) (such as Set Disjointness) has access to the inputs \( x \) and \( y \) through two separate oracles \( {\mathcal {O}}_x \) and \( {\mathcal {O}}_y \) , respectively. The restriction is that the algorithm is required to alternately make \( d \) queries to \( {\mathcal {O}}_x \) and \( d \) queries to \( {\mathcal {O}}_y \) , with input-independent computation in between queries. The model reflects a “switching delay” of \( d \) queries between a “round” of queries to \( x \) and the following “round” of queries to \( y \) . The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Round and communication complexity"

1

Pankratov, Denis. "Communication complexity and information complexity." Thesis, The University of Chicago, 2015. http://pqdtopen.proquest.com/#viewpdf?dispub=3711791.

Full text
Abstract:

Information complexity enables the use of information-theoretic tools in communication complexity theory. Prior to the results presented in this thesis, information complexity was mainly used for proving lower bounds and direct-sum theorems in the setting of communication complexity. We present three results that demonstrate new connections between information complexity and communication complexity.

In the first contribution we thoroughly study the information complexity of the smallest nontrivial two-party function: the AND function. While computing the communication complexity of AND is trivial, computing its exact information complexity presents a major technical challenge. In overcoming this challenge, we reveal that information complexity gives rise to rich geometrical structures. Our analysis of information complexity relies on new analytic techniques and new characterizations of communication protocols. We also uncover a connection of information complexity to the theory of elliptic partial differential equations. Once we compute the exact information complexity of AND, we can compute exact communication complexity of several related functions on n-bit inputs with some additional technical work. Previous combinatorial and algebraic techniques could only prove bounds of the form Θ( n). Interestingly, this level of precision is typical in the area of information theory, so our result demonstrates that this meta-property of precise bounds carries over to information complexity and in certain cases even to communication complexity. Our result does not only strengthen the lower bound on communication complexity of disjointness by making it more exact, but it also shows that information complexity provides the exact upper bound on communication complexity. In fact, this result is more general and applies to a whole class of communication problems.

In the second contribution, we use self-reduction methods to prove strong lower bounds on the information complexity of two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product mod 2 (IP). In our first result we affirm the conjecture that the information complexity of GHD is linear even under the uniform distribution. This strengthens the Ω(n) bound shown by Kerenidis et al. (2012) and answers an open problem by Chakrabarti et al. (2012). We also prove that the information complexity of IP is arbitrarily close to the trivial upper bound n as the permitted error tends to zero, again strengthening the Ω(n) lower bound proved by Braverman and Weinstein (2011). More importantly, our proofs demonstrate that self-reducibility makes the connection between information complexity and communication complexity lower bounds a two-way connection. Whereas numerous results in the past used information complexity techniques to derive new communication complexity lower bounds, we explore a generic way, in which communication complexity lower bounds imply information complexity lower bounds in a black-box manner.

In the third contribution we consider the roles that private and public randomness play in the definition of information complexity. In communication complexity, private randomness can be trivially simulated by public randomness. Moreover, the communication cost of simulating public randomness with private randomness is well understood due to Newman's theorem (1991). In information complexity, the roles of public and private randomness are reversed: public randomness can be trivially simulated by private randomness. However, the information cost of simulating private randomness with public randomness is not understood. We show that protocols that use only public randomness admit a rather strong compression. In particular, efficient simulation of private randomness by public randomness would imply a version of a direct sum theorem in the setting of communication complexity. This establishes a yet another connection between the two areas. (Abstract shortened by UMI.)

APA, Harvard, Vancouver, ISO, and other styles
2

Ada, Anil. "Communication complexity." Thesis, McGill University, 2014. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=121119.

Full text
Abstract:
Communication complexity studies how many bits a certain number of parties need to communicate with each other in order to compute a function whose input is distributed among those parties. Although it is a natural area of investigation based on practical considerations, the main motivation comes from the myriad of applications in theoretical computer science.This thesis has three main parts, studying three different aspects of communication complexity.1. The first part is concerned with the k-party communication complexity of functions F:({0,1}^n)^k -> {0,1} in the 'number on the forehead' (NOF) model. This is a fundamental model with many applications. In this model we study composed functions f of g. These functions include most of the well-known and studied functions in communication complexity literature. A major goal is to understand which combinations of f and g lead to hard communication functions. In particular, due to important circuit applications, it is of great interest to understand how powerful the NOF model becomes when k is log n or more. Motivated by these goals, we show that there is an efficient O(log^3 n) cost simultaneous protocol for sym of g when k > 1+log n, sym is any symmetric function and g is any function. This class of functions includes some functions that were previously conjectured to be hard and our result rules this class out for possible very important circuit complexity applications. We also give Ramsey theoretic applications of our efficient protocol. In the setting of k < log n, we study more closely functions of the form majority of g, mod_m of g, and nor of g, where the latter two are generalizations of the well-known functions Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of g. As the main application, we answer a question posed by Babai et al. (SIAM Journal on Computing, 33:137--166, 2004) and determine the communication complexity of majority of qcsb, where qcsb is the "quadratic character of the sum of the bits" function. 2. The second part is about Fourier analysis of symmetric boolean functions and its applications in communication complexity and other areas. The spectral norm of a boolean function f:{0,1}^n -> {0,1} is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as communication complexity, learning theory and circuit complexity. We give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as r(f)log(n/r(f)) where r(f) = max(r_0,r_1), and r_0 and r_1 are the smallest integers less than n/2 such that f(x) or f(x)parity(x) is constant for all x with x_1 + ... + x_n in [r_0, n-r_1]. We present some applications to the decision tree and communication complexity of symmetric functions. 3. The third part studies privacy in the context of communication complexity: how much information do the players reveal about their input when following a communication protocol? The unattainability of perfect privacy for many functions motivates the study of approximate privacy. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) defined notions of worst-case as well as average-case approximate privacy, and presented several interesting upper bounds, and some open problems for further study. In this thesis, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey Auction, which is the canonical example of a truthful auction. We also prove exponential lower bounds on the approximate privacy of protocols computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al.
La complexité de communication étudie combien de bits un groupe de joueurs donné doivent échanger entre eux pour calculer une function dont l'input est distribué parmi les joueurs. Bien que ce soit un domaine de recherche naturel basé sur des considérations pratiques, la motivation principale vient des nombreuses applications théoriques.Cette thèse comporte trois parties principales, étudiant trois aspects de la complexité de communication.1. La première partie discute le modèle 'number on the forehead' (NOF) dans la complexité de communication à plusieurs joueurs. Il s'agit d'un modèle fondamental en complexité de communication, avec des applications à la complexité des circuits, la complexité des preuves, les programmes de branchement et la théorie de Ramsey. Dans ce modèle, nous étudions les fonctions composeés f de g. Ces fonctions comprennent la plupart des fonctions bien connues qui sont étudiées dans la littérature de la complexité de communication. Un objectif majeur est de comprendre quelles combinaisons de f et g produisent des compositions qui sont difficiles du point de vue de la communication. En particulier, à cause de l'importance des applications aux circuits, il est intéressant de comprendre la puissance du modèle NOF quand le nombre de joueurs atteint ou dépasse log n. Motivé par ces objectifs nous montrons l'existence d'un protocole simultané efficace à k joueurs de coût O(log^3 n) pour sym de g lorsque k > 1 + log n, sym est une function symmétrique quelconque et g est une fonction arbitraire. Nous donnons aussi des applications de notre protocole efficace à la théorie de Ramsey.Dans le contexte où k < log n, nous étudions de plus près des fonctions de la forme majority de g, mod_m de g et nor de g, où les deux derniers cas sont des généralisations des fonctions bien connues et très étudiées Inner Product et Disjointness respectivement. Nous caractérisons la complexité de communication de ces fonctions par rapport au choix de g.2. La deuxième partie considère les applications de l'analyse de Fourier des fonctions symmétriques à la complexité de communication et autres domaines. La norme spectrale d'une function booléenne f:{0,1}^n -> {0,1} est la somme des valeurs absolues de ses coefficients de Fourier. Nous donnons une caractérisation combinatoire pour la norme spectrale des fonctions symmétriques. Nous montrons que le logarithme de la norme spectrale est du même ordre de grandeur que r(f)log(n/r(f)), avec r(f) = max(r_0,r_1) où r_0 et r_1 sont les entiers minimaux plus petits que n/2 pour lesquels f(x) ou f(x)parity(x) est constant pour tout x tel que x_1 + ... + x_n à [r_0,n-r_1]. Nous présentons quelques applications aux arbres de décision et à la complexité de communication des fonctions symmétriques.3. La troisième partie étudie la confidentialité dans le contexte de la complexité de communication: quelle quantité d'information est-ce que les joueurs révèlent sur leur input en suivant un protocole donné? L'inatteignabilité de la confidentialité parfaite pour plusieurs fonctions motivent l'étude de la confidentialité approximative. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) ont défini des notions de confidentialité approximative dans le pire cas et dans le cas moyen, et ont présenté plusieurs bornes supérieures intéressantes ainsi que quelques questions ouvertes. Dans cette thèse, nous obtenons des bornes asymptotiques précises, pour le pire cas aussi bien que pour le cas moyen, sur l'échange entre la confidentialité approximative de protocoles et le coût de communication pour les enchères Vickrey Auction, qui constituent l'exemple canonique d'une enchère honnête. Nous démontrons aussi des bornes inférieures exponentielles sur la confidentialité approximative de protocoles calculant la function Intersection, indépendamment du coût de communication. Ceci résout une conjecture de Feigenbaum et al.
APA, Harvard, Vancouver, ISO, and other styles
3

Chen, Lijie S. M. Massachusetts Institute of Technology. "Fine-grained complexity meets communication complexity." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/122754.

Full text
Abstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 215-229).
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 proved for numerous exact problems from all fields of computer science, showing that many text-book algorithms are in fact optimal. For many natural problems, a fast approximation algorithm would be as important as fast exact algorithms. So it would be interesting to show hardness for approximation algorithms as well. But we had few techniques to prove tight hardness for approximation problems in P--In particular, the celebrated PCP Theorem, which proves similar approximation hardness in the world of NP-completeness, is not fine-grained enough to yield interesting conditional lower bounds for approximation problems in P.
In 2017, a breakthrough work of Abboud, Rubinstein and Williams [12] established a framework called "Distributed PCP", and applied that to show conditional hardness (under SETH) for several fundamental approximation problems in P. The most interesting aspect of their work is a connection between fine-grained complexity and communication complexity, which shows Merlin-Arther communication protocols can be utilized to give fine-grained reductions between exact and approximation problems. In this thesis, we further explore the connection between fine-grained complexity and communication complexity. More specifically, we have two sets of results. In the first set of results, we consider communication protocols other than Merlin-Arther protocols in [12] and show that they can be used to construct other fine-grained reductions between problems. [sigma]₂ Protocols and An Equivalence Class for Orthogonal Vectors (OV).
First, we observe that efficient [sigma]₂[superscripts cc] protocols for a function imply fine-grained reductions from a certain related problem to OV. Together with other techniques including locality-sensitive hashing, we establish an equivalence class for OV with O(log n) dimensions, including Max-IP/Min-IP, approximate Max-IP/Min-IP, and approximate bichromatic closest/further pair. · NP · UPP Protocols and Hardness for Computational Geometry Problems in 2⁰([superscript log*n]) Dimensions. Second, we consider NP · UPP protocols which are the relaxation of Merlin-Arther protocols such that Alice and Bob only need to be convinced with probability > 1/2 instead of > 2/3.
We observe that NP · UPP protocols are closely connected to Z-Max-IP problem in very small dimensions, and show that Z-Max-IP, l₂₋-Furthest Pair and Bichromatic l₂-Closest Pair in 2⁰[superscript (log* n)] dimensions requires n²⁻⁰[superscript (1)] time under SETH, by constructing an efficient NP - UPP protocol for the Set-Disjointness problem. This improves on the previous hardness result for these problems in w(log² log n) dimensions by Williams [172]. · IP Protocols and Hardness for Approximation Problems Under Stronger Conjectures. Third, building on the connection between IP[superscript cc] protocols and a certain alternating product problem observed by Abboud and Rubinstein [11] and the classical IP = PSPACE theorem [123, 155]. We show that several finegrained problems are hard under conjectures much stronger than SETH (e.g., the satisfiability of n⁰[superscript (1)]-depth circuits requires 2(¹⁻⁰[superscript (1)n] time).
In the second set of results, we utilize communication protocols to construct new algorithms. · BQP[superscript cc] Protocols and Approximate Counting Algorithms. Our first connection is that a fast BQP[superscript cc] protocol for a function f implies a fast deterministic additive approximate counting algorithm for a related pair counting problem. Applying known BQP[superscript cc] protocols, we get fast deterministic additive approximate counting algorithms for Count-OV (#OV), Sparse Count-OV and Formula of SYM circuits. · AM[superscript cc]/PH[superscript cc] Protocols and Efficient SAT Algorithms. Our second connection is that a fast AM[superscript cc] (or PH[superscript cc]) protocol for a function f implies a faster-than-bruteforce algorithm for a related problem.
In particular, we show that if the Longest Common Subsequence (LCS) problem admits a fast (computationally efficient) PH[superscript cc] protocol (polylog(n) complexity), then polynomial-size Formula-SAT admits a 2[superscript n-n][superscript 1-[delta]] time algorithm for any constant [delta] > 0, which is conjectured to be unlikely by a recent work of Abboud and Bringmann [6].
by Lijie Chen.
S.M.
S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
APA, Harvard, Vancouver, ISO, and other styles
4

Dam, Wim van. "Nonlocality and communication complexity." Thesis, University of Oxford, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.325982.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Lerays, Virginie. "Quantum nonlocality and communication complexity." Paris 7, 2014. http://www.theses.fr/2014PA077151.

Full text
Abstract:
Les fondements de l'informatique ont subi un bouleversement face à l'émergence du calcul quantique comme nouveau modèle de calcul. Nous nous intéresserons dans cette thèse à la complexité de la communication, vue sous l'angle de la théorie de l'information quantique. En complexité de la communication, on cherche à savoir combien de communication il faut pour résoudre des problèmes où les entrées sont réparties entre les entités de calcul. Cette thèse présente un moyen d'obtenir des bornes inférieures en complexité de la communication en exploitant des idées liées à l'étude de phénomènes quantiques tels que la nonlocalité. Ces méthodes sont alors comparées aux méthodes déjà connues dans la littérature et permettent d'obtenir une nouvelle famille d'inégalités de Bell. Nous montrons aussi dans cette thèse, en utilisant les connections entre complexité de la communication et nonlocalité quantique, que toutes les bornes inférieures connues utilisées en complexité de la communication sont des bornes inférieures pour la complexité de l'information. Ceci renforce l'idée que ces deux quantités sont équivalentes et permet d'obtenir plusieurs résultats de sommes directes en complexité de la communication pour des fonctions souvent étudiées
Quantum computing raises a lot of questions related to the foundations of computing. We study, in this thesis, a complexity model called communication complexity, where we study the amount of communication required to solve a distributed task. We study this model from the perspective of quantum information theory. This thesis introduces a new way of obtaining lower bounds on communication complexity, using ideas developed in the study of quantum nonlocality. These methods are compared to previously known lower-bound methods and allow us to define a new family of Bell inequalities. We also prove in this thesis that ail previously known lower bounds for communication complexity are also lower bounds on information complexity. This witnesses the potential equivalence between these two measures of complexity and allows us to obtain direct sum results on the communication complexity of very-well studied functions
APA, Harvard, Vancouver, ISO, and other styles
6

Lacayo, Virginia. "Communicating Complexity: A Complexity Science Approach to Communication for Social Change." Ohio University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1367522049.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Angus, Simon Douglas Economics Australian School of Business UNSW. "Economic networks: communication, cooperation & complexity." Awarded by:University of New South Wales. Economics, 2007. http://handle.unsw.edu.au/1959.4/27005.

Full text
Abstract:
This thesis is concerned with the analysis of economic network formation. There are three novel sections to this thesis (Chapters 5, 6 and 8). In the first, the non-cooperative communication network formation model of Bala and Goyal (2000) (BG) is re-assessed under conditions of no inertia. It is found that the Strict Nash circle (or wheel) structure is still the equilibrium outcome for n = 3 under no inertia. However, a counter-example for n = 4 shows that with no inertia infinite cycles are possible, and hence the system does not converge. In fact, cycles are found to quickly dominate outcomes for n > 4 and further numerical simulations of conditions approximating no inertia (probability of updating > 0.8 to 1) indicate that cycles account for a dramatic slowing of convergence times. These results, together with the experimental evidence of Falk and Kosfeld (2003) (FK) motivate the second contribution of this thesis. A novel artificial agent model is constructed that allows for a vast strategy space (including the Best Response) and permits agents to learn from each other as was indicated by the FK results. After calibration, this model replicates many of the FK experimental results and finds that an externality exploiting ratio of benefits and costs (rather than the difference) combined with a simple altruism score is a good proxy for the human objective function. Furthermore, the inequity aversion results of FK are found to arise as an emergent property of the system. The third novel section of this thesis turns to the nature of network formation in a trust-based context. A modified Iterated Prisoners' Dilemma (IPD) model is developed which enables agents to play an additional and costly network forming action. Initially, canonical analytical results are obtained despite this modification under uniform (non-local) interactions. However, as agent network decisions are 'turned on' persistent cooperation is observed. Furthermore, in contrast to the vast majority of non-local, or static network models in the literature, it is found that a-periodic, complex dynamics result for the system in the long-run. Subsequent analysis of this regime indicates that the network dynamics have fingerprints of self-organized criticality (SOC). Whilst evidence for SOC is found in many physical systems, such dynamics have been seldom, if ever, reported in the strategic interaction literature.
APA, Harvard, Vancouver, ISO, and other styles
8

McGinty, Nigel, and nigel mcginty@defence gov au. "Reduced Complexity Equalization for Data Communication." The Australian National University. Research School of Information Sciences and Engineering, 1998. http://thesis.anu.edu.au./public/adt-ANU20050602.122741.

Full text
Abstract:
Optimal decision directed equalization techniques for time dispersive communication channels are often too complex to implement. This thesis considers reduced complexity decision directed equalization that lowers complexity demands yet retains close to optimal performance. The first part of this dissertation consists of three reduced complexity algorithms based on the Viterbi Algorithm (VA) which are: the Parallel Trellis VA (PTVA); Time Reverse Reduced State Sequence Estimation (TR-RSSE); and Forward-Backward State Sequence Detection (FBSSD). The second part of the thesis considers structural modifications of the Decision Feedback Equalizer (DFE), which is a special derivative of the VA, specifically, optimal vector quantization for fractionally spaced DFEs, and extended stability regions for baud spaced DFEs using passivity analysis are investigated.¶ For a special class of sparse channels the VA can be decomposed over a number of independent parallel trellises. This decomposition will be called the Parallel Trellis Viterbi Algorithm and can have lower complexity than the VA yet it retains optimal performance. By relaxing strict sparseness constraints on the channel a sub-optimal approach is proposed which keeps complexity low and obtains good performance.¶ Reduced State Sequence Estimation (RSSE) is a popular technique to reduce complexity. However, its deficiency can be the inability to adequately equalize non-minimum phase channels. For channels that have energy peaks in the tail of the impulse response (post-cursor dominant) RSSE's complexity must be close to the VA or performance will be poor. Using a property of the VA which makes it invariant to channel reversal, TR-RSSE is proposed to extend application of RSSE to post-cursor dominant channels.¶ To further extend the class of channels suitable for RSSE type processing, FBSSD is suggested. This uses a two pass processing method, and is suited to channels that have low energy pre and post-cursor. The first pass generates preliminary estimates used in the second pass to aid the decision process. FBSSD can range from RSSE to TR-RSSE depending on parameter settings.¶ The DFE is obtained when the complexity of RSSE is minimized. Two characterizing properties of the DFE, which are addressed in this thesis, are feedback and quantization. A novel fractionally spaced (FS) DFE structure is presented which allows the quantizer to be generalized relative to the quantizer used in conventional FS-DFEs. The quantizer can be designed according to a maximum a posteriori criterion which takes into account a priori statistical knowledge of error occurrences. A radically different quantizer can be obtained using this technique which can result in significant performance improvements.¶ Due to the feedback nature of the DFE a form of stability can be considered. After a decision error occurs, a stable DFE will, after some finite time and in the absence of noise, operate error free. Passivity analysis provides sufficient conditions to determine a class of channels which insures a DFE will be stable. Under conditions of short channels and small modulation alphabets, it is proposed that conventional passivity analysis can be extended to account for varying operator gains, leading to weaker sufficient conditions for stability (larger class of channels).
APA, Harvard, Vancouver, ISO, and other styles
9

Tesson, Pascal. "An algebraic approach to communication complexity." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0026/MQ50894.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Dhulipala, Anand. "On communication complexity and universal compression." Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2007. http://wwwlib.umi.com/cr/ucsd/fullcit?p3284204.

Full text
Abstract:
Thesis (Ph. D.)--University of California, San Diego, 2007.
Title from first page of PDF file (viewed January 10, 2008). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 93-95).
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Round and communication complexity"

1

Noam, Nisan, ed. Communication complexity. New York: Cambridge University Press, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Hromkovič, Juraj. Communication complexity and parallel computing. Berlin: Springer, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Hromkovič, Juraj. Communication Complexity and Parallel Computing. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Communication complexity and parallel computing. New York: Springer, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

The complexity of human communication. Cresskill, N.J: Hampton Press, 2008.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

The complexity of human communication. 2nd ed. New York: Hampton Press, 2013.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Barthelemy, Jean-Pierre. Algorithmic complexity and communication problems. London: UCL Press, 1996.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Jurdziński, Tomasz, and Stefan Schmid, eds. Structural Information and Communication Complexity. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-79527-6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Parter, Merav, ed. Structural Information and Communication Complexity. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-09993-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Censor-Hillel, Keren, and Michele Flammini, eds. Structural Information and Communication Complexity. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-24922-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Round and communication complexity"

1

Kublenz, Simeon, Sebastian Siebertz, and Alexandre Vigny. "Constant Round Distributed Domination on Graph Classes with Bounded Expansion." In Structural Information and Communication Complexity, 334–51. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-79527-6_19.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Kishore, Ravi, Ashutosh Kumar, Chiranjeevi Vanarasa, and Srinathan Kannan. "Round-Optimal Perfectly Secret Message Transmission with Linear Communication Complexity." In Lecture Notes in Computer Science, 33–50. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-17470-9_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Alistarh, Dan, Hagit Attiya, Rachid Guerraoui, and Corentin Travers. "Early Deciding Synchronous Renaming in O( logf ) Rounds or Less." In Structural Information and Communication Complexity, 195–206. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31104-8_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Montealegre, Pedro, Sebastian Perez-Salazar, Ivan Rapaport, and Ioan Todinca. "Two Rounds Are Enough for Reconstructing Any Graph (Class) in the Congested Clique Model." In Structural Information and Communication Complexity, 134–48. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-01325-7_15.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ben-Basat, Ran, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman. "A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in $$O(\log N\log \varDelta /\log ^2\log \varDelta )$$ Rounds." In Structural Information and Communication Complexity, 226–36. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-01325-7_21.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

di Crescenzo, Giovanni, Kouichi Sakurai, and Moti Yung. "Zero-knowledge proofs of decision power: New protocols and optimal round-complexity." In Information and Communications Security, 17–27. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/bfb0028458.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Mowles, Chris. "Complex communication." In Complexity, 82–102. London: Routledge, 2021. http://dx.doi.org/10.4324/9781003002840-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Mowles, Chris. "Complex communication." In Complexity, 82–102. London: Routledge, 2021. http://dx.doi.org/10.4324/9781003002840-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Orlitsky, A., and A. El Gamal. "Communication Complexity." In Complexity in Information Theory, 16–61. New York, NY: Springer New York, 1998. http://dx.doi.org/10.1007/978-1-4612-3774-7_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Chakrabarti, Amit. "Communication Complexity." In Encyclopedia of Algorithms, 349–57. New York, NY: Springer New York, 2016. http://dx.doi.org/10.1007/978-1-4939-2864-4_799.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Round and communication complexity"

1

Kremer, Ilan, Noam Nisan, and Dana Ron. "On randomized one-round communication complexity." In the twenty-seventh annual ACM symposium. New York, New York, USA: ACM Press, 1995. http://dx.doi.org/10.1145/225058.225277.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ganesh, Chaya, and Arpita Patra. "Broadcast Extensions with Optimal Communication and Round Complexity." In PODC '16: ACM Symposium on Principles of Distributed Computing. New York, NY, USA: ACM, 2016. http://dx.doi.org/10.1145/2933057.2933082.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Woodworth, Blake, Brian Bullins, Ohad Shamir, and Nathan Srebro. "The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication (Extended Abstract)." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/751.

Full text
Abstract:
We resolve the min-max complexity of distributed stochastic convex optimization (up to a log factor) in the intermittent communication setting, where M machines work in parallel over the course of R rounds of communication to optimize the objective, and during each round of communication, each machine may sequentially compute K stochastic gradient estimates. We present a novel lower bound with a matching upper bound that establishes an optimal algorithm.
APA, Harvard, Vancouver, ISO, and other styles
4

Brody, Joshua, and Amit Chakrabarti. "A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences." In 2009 24th Annual IEEE Conference on Computational Complexity (CCC). IEEE, 2009. http://dx.doi.org/10.1109/ccc.2009.31.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Braverman, Mark, Ankit Garg, Young Kun Ko, Jieming Mao, and Dave Touchette. "Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness." In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2015. http://dx.doi.org/10.1109/focs.2015.53.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Jin Seek Choi, Mijeong Yang, and Tae Il Kim. "Complexity analysis of a dual round-robin iSLIP (DiSLIP) scheduling scheme." In 8th International Conference on Advanced Communication Technology. IEEE, 2006. http://dx.doi.org/10.1109/icact.2006.206406.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Nisan, Noam, and Avi Widgerson. "Rounds in communication complexity revisited." In the twenty-third annual ACM symposium. New York, New York, USA: ACM Press, 1991. http://dx.doi.org/10.1145/103418.103463.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Mendoza-Granada, Fabricio, and Marcos Villagra. "Number-On-Forehead Communication Complexity of Data Clustering with Sunflowers." In IV Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/etc.2019.6394.

Full text
Abstract:
We study the problem of performing data clustering in a distributed setting, which is a problem that may arise in many practical areas such as machine learning and data analysis. The way in which the sites communicate and the way data is allocated define a model of communication. We develop a protocol to compute distributed clustering in the Number on Forehead model of communication complexity. In our model, we requiere that each site is aware of all clusters in its own data and all data allocated among sites define a sunflower. We show that there exists a two round communication protocol for data clustering where each site knows an to all clusters.
APA, Harvard, Vancouver, ISO, and other styles
9

Jain, Rahul, Attila Pereszlenyi, and Penghui Yao. "A Direct Product Theorem for the Two-Party Bounded-Round Public-Coin Communication Complexity." In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2012. http://dx.doi.org/10.1109/focs.2012.42.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Patt-Shamir, Boaz, and Marat Teplitsky. "The round complexity of distributed sorting." In the 30th annual ACM SIGACT-SIGOPS symposium. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/1993806.1993851.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Round and communication complexity"

1

Awerbuch, B., and R. G. Gallager. Communication Complexity of Distributed Shortest Path Algorithms. Fort Belvoir, VA: Defense Technical Information Center, June 1985. http://dx.doi.org/10.21236/ada156049.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Luo, Zhi-Quan, and John N. Tsitsiklis. On the Communication Complexity of Distributed Algebraic Computation. Fort Belvoir, VA: Defense Technical Information Center, February 1989. http://dx.doi.org/10.21236/ada205784.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Luo, Zhi-Quan, and John N. Tsitsiklis. On the Communication Complexity of Solving a Polynomial Equation. Fort Belvoir, VA: Defense Technical Information Center, July 1989. http://dx.doi.org/10.21236/ada211945.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Rose, Andrew M., Donna J. Mayo, and Janice C. Redish. Modeling the Speech Communication Effect on Performance: Message Complexity. Fort Belvoir, VA: Defense Technical Information Center, June 1991. http://dx.doi.org/10.21236/ada254711.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Taylor, Karen, and Daniel Blitzer. The Influence of Communication on the Complexity of Connected Lighting Systems. Office of Scientific and Technical Information (OSTI), July 2021. http://dx.doi.org/10.2172/1814141.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Hahne, Ellen L., and Robert G. Gallager. Round Robin Scheduling for Fair Flow Control in Data Communication Networks. Fort Belvoir, VA: Defense Technical Information Center, March 1986. http://dx.doi.org/10.21236/ada166728.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Perdigão, Rui A. P. Beyond Quantum Security with Emerging Pathways in Information Physics and Complexity. Synergistic Manifolds, June 2022. http://dx.doi.org/10.46337/220602.

Full text
Abstract:
Information security and associated vulnerabilities have long been a pressing challenge, from the fundamental scientific backstage to the frontline across the most diverse sectors of society. At the tip of the iceberg of this problem, the citizens immediately feel that the reservation of privacy and the degradation of the quality and security of the information and communication on which they depend for the day-to-day activities, already of crucial relevance, are at stake. Naturally though, the challenges do not end there. There is a whole infrastructure for storing information, processing and communication, whose security and reliability depend on key sectors gearing modern society – such as emergency communication systems (medical, civil and environmental protection, among others), transportation and geographic information, the financial communications systems at the backbone of day-to-day transactions, the information and telecommunications systems in general. And crucially the entire defence ecosystem that in essence is a stalwart in preventing our civilisation to self-annihilate in full fulfilment of the second principle of thermodynamics. The relevance of the problem further encompasses the preservation of crucial values such as the right to information, security and integrity of democratic processes, internal administration, justice, defence and sovereignty, ranging from the well-being of the citizen to the security of the nation and beyond. In the present communication, we take a look at how to scientifically and technically empower society to address these challenges, with the hope and pragmatism enabled by our emerging pathways in information physics and complexity. Edging beyond classical and quantum frontiers and their vulnerabilities to unveil new principles, methodologies and technologies at the core of the next generation system dynamic intelligence and security. To illustrate the concepts and tools, rather than going down the road of engineered systems that we can ultimately control, we take aim at the bewildering complexity of nature, deciphering new secrets in the mathematical codex underlying its complex coevolutionary phenomena that so heavily impact our lives, and ultimately bringing out novel insights, methods and technologies that propel information physics and security beyond quantum frontiers.
APA, Harvard, Vancouver, ISO, and other styles
8

Willis, Craig, Will Hughes, and Sergiusz Bober. ECMI Minorities Blog. National and Linguistic Minorities in the Context of Professional Football across Europe: Five Examples from Non-kin State Situations. European Centre for Minority Issues, December 2022. http://dx.doi.org/10.53779/bvkl7633.

Full text
Abstract:
Football clubs are often analysed by scholars as ‘imagined communities’, for no fan of any team will ever meet, or even be aware of most of their fellow supporters on an individual level. They are also simultaneously one of the most tribal phenomena of the twenty-first century, comparable to religion in terms of the complexity of rituals, their rhythm and overall organizational intricacies, yet equally inseparable from economics and politics. Whilst, superficially, the events of sporting fixtures carry little political significance, for many of Europe’s national and linguistic minorities football fandom takes on an extra dimension of identity – on an individual and collective scale, acting as a defining differentiation from the majority society. This blogpost analyses five clubs from non-kin state settings, with the intention to assess how different aspects of minority identities affect their fan bases, communication policies and other practices.
APA, Harvard, Vancouver, ISO, and other styles
9

Perdigão, Rui A. P. Information physics and quantum space technologies for natural hazard sensing, modelling and prediction. Meteoceanics, September 2021. http://dx.doi.org/10.46337/210930.

Full text
Abstract:
Disruptive socio-natural transformations and climatic change, where system invariants and symmetries break down, defy the traditional complexity paradigms such as machine learning and artificial intelligence. In order to overcome this, we introduced non-ergodic Information Physics, bringing physical meaning to inferential metrics, and a coevolving flexibility to the metrics of information transfer, resulting in new methods for causal discovery and attribution. With this in hand, we develop novel dynamic models and analysis algorithms natively built for quantum information technological platforms, expediting complex system computations and rigour. Moreover, we introduce novel quantum sensing technologies in our Meteoceanics satellite constellation, providing unprecedented spatiotemporal coverage, resolution and lead, whilst using exclusively sustainable materials and processes across the value chain. Our technologies bring out novel information physical fingerprints of extreme events, with recently proven records in capturing early warning signs for extreme hydro-meteorologic events and seismic events, and do so with unprecedented quantum-grade resolution, robustness, security, speed and fidelity in sensing, processing and communication. Our advances, from Earth to Space, further provide crucial predictive edge and added value to early warning systems of natural hazards and long-term predictions supporting climatic security and action.
APA, Harvard, Vancouver, ISO, and other styles
10

Perdigão, Rui A. P. New Horizons of Predictability in Complex Dynamical Systems: From Fundamental Physics to Climate and Society. Meteoceanics, October 2021. http://dx.doi.org/10.46337/211021.

Full text
Abstract:
Discerning the dynamics of complex systems in a mathematically rigorous and physically consistent manner is as fascinating as intimidating of a challenge, stirring deeply and intrinsically with the most fundamental Physics, while at the same time percolating through the deepest meanders of quotidian life. The socio-natural coevolution in climate dynamics is an example of that, exhibiting a striking articulation between governing principles and free will, in a stochastic-dynamic resonance that goes way beyond a reductionist dichotomy between cosmos and chaos. Subjacent to the conceptual and operational interdisciplinarity of that challenge, lies the simple formal elegance of a lingua franca for communication with Nature. This emerges from the innermost mathematical core of the Physics of Coevolutionary Complex Systems, articulating the wealth of insights and flavours from frontier natural, social and technical sciences in a coherent, integrated manner. Communicating thus with Nature, we equip ourselves with formal tools to better appreciate and discern complexity, by deciphering a synergistic codex underlying its emergence and dynamics. Thereby opening new pathways to see the “invisible” and predict the “unpredictable” – including relative to emergent non-recurrent phenomena such as irreversible transformations and extreme geophysical events in a changing climate. Frontier advances will be shared pertaining a dynamic that translates not only the formal, aesthetical and functional beauty of the Physics of Coevolutionary Complex Systems, but also enables and capacitates the analysis, modelling and decision support in crucial matters for the environment and society. By taking our emerging Physics in an optic of operational empowerment, some of our pioneering advances will be addressed such as the intelligence system Earth System Dynamic Intelligence and the Meteoceanics QITES Constellation, at the interface between frontier non-linear dynamics and emerging quantum technologies, to take the pulse of our planet, including in the detection and early warning of extreme geophysical events from Space.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Round and communication complexity' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography