More Like this

1. One-Way Communication Complexity of Minimum Vertex Cover in General Graphs

   https://doi.org/10.4230/lipics.icalp.2025.66  

   Derakhshan, Mahsa; Ghasemi, Andisheh; Rajaraman, Rajmohan (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Censor-Hillel, Keren; Grandoni, Fabrizio; Ouaknine, Joel; Puppis, Gabriele (Ed.)

   We study the communication complexity of the Minimum Vertex Cover (MVC) problem on general graphs within the k-party one-way communication model. Edges of an arbitrary n-vertex graph are distributed among k parties. The objective is for the parties to collectively find a small vertex cover of the graph while adhering to a communication protocol where each party sequentially sends a message to the next until the last party outputs a valid vertex cover of the whole graph. We are particularly interested in the trade-off between the size of the messages sent and the approximation ratio of the output solution. It is straightforward to see that any constant approximation protocol for MVC requires communicating Ω(n) bits. Additionally, there exists a trivial 2-approximation protocol where the parties collectively find a maximal matching of the graph greedily and return the subset of vertices matched. This raises a natural question: What is the best approximation ratio achievable using optimal communication of O(n)? We design a protocol with an approximation ratio of (2-2^{-k+1}+ε) and O(n) communication for any desirably small constant ε > 0, which is strictly better than 2 for any constant number of parties. Moreover, we show that achieving an approximation ratio smaller than 3/2 for the two-party case requires n^{1 + Ω(1/lg lg n)} communication, thereby establishing the tightness of our protocol for two parties. A notable aspect of our protocol is that no edges are communicated between the parties. Instead, for any 1 ≤ i < k, the i-th party only communicates a constant number of vertex covers for all edges assigned to the first i parties. An interesting consequence is that the communication cost of our protocol is O(n) bits, as opposed to the typical Ω(nlog n) bits required for many graph problems, such as maximum matching, where protocols commonly involve communicating edges. 

   more » « less
2. Resource-Efficient Common Randomness and Secret-Key Schemes

   Ghazi, Badih; Jayram, T.S. (January 2018, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space. Read More: https://epubs.siam.org/doi/10.1137/1.9781611975031.120 

   more » « less
3. New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification

   https://doi.org/10.4230/LIPIcs.ITCS.2024.53  

   Ghosh, Prantar; Shah, Vihan (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   We present novel lower bounds in the Merlin-Arthur (MA) communication model and the related annotated streaming or stream verification model. The MA communication model extends the classical communication model by introducing an all-powerful but untrusted player, Merlin, who knows the inputs of the usual players, Alice and Bob, and attempts to convince them about the output. We focus on the online MA (OMA) model where Alice and Merlin each send a single message to Bob, who needs to catch Merlin if he is dishonest and announce the correct output otherwise. Most known functions have OMA protocols with total communication significantly smaller than what would be needed without Merlin. In this work, we introduce the notion of non-trivial-OMA complexity of a function. This is the minimum total communication required when we restrict ourselves to only non-trivial protocols where Alice sends Bob fewer bits than what she would have sent without Merlin. We exhibit the first explicit functions that have this complexity superlinear - even exponential - in their classical one-way complexity: this means the trivial protocol, where Merlin communicates nothing and Alice and Bob compute the function on their own, is exponentially better than any non-trivial protocol in terms of total communication. These OMA lower bounds also translate to the annotated streaming model, the MA analogue of single-pass data streaming. We show large separations between the classical streaming complexity and the non-trivial annotated streaming complexity (for the analogous notion in this setting) of fundamental problems such as counting distinct items, as well as of graph problems such as connectivity and k-connectivity in a certain edge update model called the support graph turnstile model that we introduce here. 

   more » « less
4. High-dimensional encryption in optical fibers using spatial modes of light and machine learning

   https://doi.org/10.1088/2632-2153/ac7f1b  

   Lollie, Michelle L; Mostafavi, Fatemeh; Bhusal, Narayan; Hong, Mingyuan; You, Chenglong; León-Montiel, Roberto de; Magaña-Loaiza, Omar S; Quiroz-Juárez, Mario A (July 2022, Machine Learning: Science and Technology)

   Abstract The ability to engineer the spatial wavefunction of photons has enabled a variety of quantum protocols for communication, sensing, and information processing. These protocols exploit the high dimensionality of structured light enabling the encoding of multiple bits of information in a single photon, the measurement of small physical parameters, and the achievement of unprecedented levels of security in schemes for cryptography. Unfortunately, the potential of structured light has been restrained to free-space platforms in which the spatial profile of photons is preserved. Here, we make an important step forward to using structured light for fiber optical communication. We introduce a classical encryption protocol in which the propagation of high-dimensional spatial modes in multimode fibers is used as a natural mechanism for encryption. This provides a secure communication channel for data transmission. The information encoded in spatial modes is retrieved using artificial neural networks, which are trained from the intensity distributions of experimentally detected spatial modes. Our on-fiber communication platform allows us to use single spatial modes for information encoding as well as the high-dimensional superposition modes for bit-by-bit and byte-by-byte encoding respectively. This protocol enables one to recover messages and images with almost perfect accuracy. Our classical smart protocol for high-dimensional encryption in optical fibers provides a platform that can be adapted to address increased per-photon information capacity at the quantum level, while maintaining the fidelity of information transfer. This is key for quantum technologies relying on structured fields of light, particularly those that are challenged by free-space propagation. 

   more » « less
5. On Simultaneous Two-Player Combinatorial Auctions

   Braverman, Mark; Mao, Jieming; Weinberg, S. Matthew (January 2018, Symposium on Discrete Algorithms)

   We consider the following communication problem: Alice and Bob each have some valuation functions $$v_1(\cdot)$$ and $$v_2(\cdot)$$ over subsets of $$m$$ items, and their goal is to partition the items into $$S, \bar{S}$$ in a way that maximizes the welfare, $$v_1(S) + v_2(\bar{S})$$. We study both the allocation problem, which asks for a welfare-maximizing partition and the decision problem, which asks whether or not there exists a partition guaranteeing certain welfare, for binary XOS valuations. For interactive protocols with $poly(m)$ communication, a tight 3/4-approximation is known for both [Fei06,DS06]. For interactive protocols, the allocation problem is provably harder than the decision problem: any solution to the allocation problem implies a solution to the decision problem with one additional round and $$\log m$$ additional bits of communication via a trivial reduction. Surprisingly, the allocation problem is provably easier for simultaneous protocols. Specifically, we show: 1) There exists a simultaneous, randomized protocol with polynomial communication that selects a partition whose expected welfare is at least $3/4$ of the optimum. This matches the guarantee of the best interactive, randomized protocol with polynomial communication. 2) For all $$\varepsilon > 0$$, any simultaneous, randomized protocol that decides whether the welfare of the optimal partition is $$\geq 1$$ or $$\leq 3/4 - 1/108+\varepsilon$$ correctly with probability $> 1/2 + 1/ poly(m)$ requires exponential communication. This provides a separation between the attainable approximation guarantees via interactive ($3/4$) versus simultaneous ($$\leq 3/4-1/108$$) protocols with polynomial communication. In other words, this trivial reduction from decision to allocation problems provably requires the extra round of communication. We further discuss the implications of our results for the design of truthful combinatorial auctions in general, and extensions to general XOS valuations. In particular, our protocol for the allocation problem implies a new style of truthful mechanisms. 

   more » « less