Is a two-party function, possibly with randomized output, securely computable? We provide a finite procedure to answer this question, thereby settling a foundational, three-decade-old open problem in secure computation and information complexity.Beaver-Chor-Kushilevitz [11], [22], [8] answered this question for deterministic output functions. Basu et al. [3] recently gave a geometric characterization of randomized functions securely computable with bounded communication complexity. Randomized functions can have arbitrarily high communication complexity, even for fixed input-output sets [5]. Without an upper bound on the communication complexity, the decidability of the question of whether a given two-party function with randomized output is securely computable was a formidable challenge.We reduce answering this question to proving specific lamination hulls are semi-algebraic. Lamination hulls are an infinite union of recursively defined sets independently motivated by the hydrodynamics literature. We connect this technical objective to solving a system of linear inequalities over convex sets in high dimensions, where inequalities represent the natural containment relation. We present a Gaussian elimination-inspired algorithm to compute the smallest simultaneous solutions to such systems. After that, using these solutions, we prove that our lamination hulls are semi-algebraic.Our technical solution introduces a novel set operator called positive geometric join. In our application context, it characterizes algebraically well-behaved sets that generalize polytopes, which we call hemihedra. The positive geometric join operator and hemihedral sets should interest the broader mathematics and computer science community. These advancements should help further information complexity investigations more broadly via the recently established connection by Basu et al. [3].

What is the round and communication complexity of secure computation? The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) answer this question for computations with deterministic output. However, this question has remained unanswered for computations with randomized output. Our work answers this question for two-party secure function evaluation functionalities. We introduce a geometric encoding of all candidate secure protocols for a given computation as points in a high-dimensional space. The following results follow by analyzing the properties of these sets of points.1)It is decidable to determine if a given computation has a secure protocol within round or communication constraints.2)We construct one such protocol if it exists.3)Otherwise, we present an obstruction to achieving security.Our technical contributions imply new information complexity bounds for secure computation.

Ben-Or and Linial (1985) introduced the full information model for coin-tossing protocols involving$n$-processors with unbounded computational power using a common broadcast channel for all their communications. A bias-$X$coin-tossing protocol outputs 1 with probability$X$; otherwise, it outputs 0 with probability ($1-X$). A coin-tossing protocol's insecurity is the maximum change in the output distribution (in the statistical distance) that an adversary can cause. This work considers an adversary who monitors the protocol's communication and intervenes at most once by restarting the processor who just broadcast her message. For a given tolerance$\varepsilon$, our objective is to use the minimum number of processors, ensuring that this adversary can only change the output distribution by at most$\epsilon$. Historically, the “threshold coin-tossing protocols” have been optimal or asymptotically optimal against various adversary models. However, for our model, Khorasgani, Maji, and Mukherjee (2019) prove the existence of coin-tossing protocols that achieve the same tolerance as the threshold protocols using a smaller number of processors. Unfortunately, their protocol is not computationally efficient. Towards this objective, for any$x\in(0,1)$and$n\in \mathbb{N}$, this paper presents computationally efficient coin-tossing protocols approximating the new protocols of Khorasgani, Maji, and Mukherjee (2019). This protocol's running time is linear in the inverse of the accuracy parameter of this approximation, which can be set arbitrarily small.

Ben-Or and Linial (1985) introduced the full information model for coin-tossing protocols involving$n$processors with unbounded computational power using a common broadcast channel for all their communications. For most adversarial settings, the characterization of the exact or asymptotically optimal protocols remains open. Furthermore, even for the settings where near-optimal asymptotic constructions are known, the exact constants or poly-logarithmic multiplicative factors involved are not entirely well-understood. This work studies$n$-processor coin-tossing protocols where every processor broadcasts an arbitrary-length message once. An adaptive Byzantine adversary, based on the messages broadcast so far, can corrupt$k=1$processor. A bias-$X$coin-tossing protocol outputs 1 with probability$X$; otherwise, it outputs 0 with probability ($1-X$). A coin-tossing protocol's insecurity is the maximum change in the output distribution (in the statistical distance) that a Byzantine adversary can cause. Our objective is to identify bias-$X$coin-tossing protocols achieving near-optimal minimum insecurity for every$X\in[0,1]$. Lichtenstein, Linial, and Saks (1989) studied bias-$X$coin-tossing protocols in this adversarial model where each party broadcasts an independent and uniformly random bit. They proved that the elegant “threshold coin-tossing protocols” are optimal for all$n$and$k$. Furthermore, Goldwasser, Kalai, and Park (2015), Kalai, Komargodski, and Raz (2018), and Haitner and Karidi-Heller (2020) prove that$k=\mathcal{O}(\sqrt{n} \cdot \mathsf{polylog}(n)$) corruptions suffice to fix the output of any bias-$X$coin-tossing protocol. These results encompass parties who send arbitrary-length messages, and each processor has multiple turns to reveal its entire message. We use an inductive approach to constructing coin-tossing protocols using a potential function as a proxy for measuring any bias-$X$coin-tossing protocol's susceptibility to attacks in our adversarial model. Our technique is inherently constructive and yields protocols that minimize the potential function. It is incidentally the case that the threshold protocols minimize the potential function, even for arbitrary-length messages. We demonstrate that these coin-tossing protocols' insecurity is a 2-approximation of the optimal protocol in our adversarial model. For any other$X\in[0,1]$that threshold protocols cannot realize, we prove that an appropriate (convex) combination of the threshold protocols is a 4-approximation of the optimal protocol. Finally, these results entail new (vertex) isoperimetric inequalities for density-$X$subsets of product spaces of arbitrary-size alphabets.

In this paper, we study the asymptotic throughput capacity of a static multi-channel multi-interface infrastructure wireless mesh network (InfWMN) wherein each infrastructure node has m interfaces and c channels of unequal bandwidth are available. First, an upper bound on the InfWMN per-user capacity is established. Then, the feasible lower bound is derived by construction. We prove that both lower and upper bounds are tight. We limit our analysis for more practical case of$\mathrm{m} \le \mathrm{c}$. However, for the asymptotic upper bound, our analysis can be used for the general case in which there is no constraint on m and c. Our study shows that in such a network with Ncrandomly distributed mesh clients, Nrregularly placed mesh routers, and Nggateways, the asymptotic per-client throughput capacity has different bounds, which depend on the ratio between the total available bandwidth for the network and the sum of m first greatest data rates of c available channels, i.e.,$\sum \limits_{\mathrm{j} = 1}^\mathrm{C} \mathrm{w}_\mathrm{j} / \sum \limits_{\mathrm{j} = 1}^\mathrm{m} \mathrm{w}_\mathrm{j}$. The results of this paper are more general compared to the existing published researches. In addition, in the case that$\mathrm{w}_\mathrm{i} = \mathrm{W}/\mathrm{c} \forall \mathrm{i},\mathrm{}1 \le \mathrm{i} \le \mathrm{c}$, our results reduce to the previously reported studies. This implies that our study is comprehensive compared to the formerly published researches.