We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent "Polynomial code" constructions in recovery threshold, i.e., the required number of ...successful workers. When a fixed <inline-formula> <tex-math notation="LaTeX">1/m </tex-math></inline-formula> fraction of each matrix can be stored at each worker node, Polynomial codes require <inline-formula> <tex-math notation="LaTeX">m^{2} </tex-math></inline-formula> successful workers, while our MatDot codes only require <inline-formula> <tex-math notation="LaTeX">2m-1 </tex-math></inline-formula> successful workers. However, MatDot codes have higher computation cost per worker and higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Furthermore, we propose "PolyDot" coding that interpolates between Polynomial codes and MatDot codes to trade off computation/communication costs and recovery thresholds. Finally, we demonstrate a novel coding technique for multiplying <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> matrices (<inline-formula> <tex-math notation="LaTeX">n \geq 3 </tex-math></inline-formula>) using ideas from MatDot and PolyDot codes.
We present an algorithm that computes the product of two n-bit integers in O(n log n) bit operations, thus confirming a conjecture of Schönhage and Strassen from 1971. Our complexity analysis takes ...place in the multitape Turing machine model, with integers encoded in the usual binary representation. Central to the new algorithm is a novel “Gaussian resampling” technique that enables us to reduce the integer multiplication problem to a collection of multidimensional discrete Fourier transforms over the complex numbers, whose dimensions are all powers of two. These transforms may then be evaluated rapidly by means of Nussbaumer's fast polynomial transforms.
A Survey on Network Embedding Cui, Peng; Wang, Xiao; Pei, Jian ...
IEEE transactions on knowledge and data engineering,
05/2019, Letnik:
31, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Network embedding assigns nodes in a network to low-dimensional representations and effectively preserves the network structure. Recently, a significant amount of progresses have been made toward ...this emerging network analysis paradigm. In this survey, we focus on categorizing and then reviewing the current development on network embedding methods, and point out its future research directions. We first summarize the motivation of network embedding. We discuss the classical graph embedding algorithms and their relationship with network embedding. Afterwards and primarily, we provide a comprehensive overview of a large number of network embedding methods in a systematic manner, covering the structure- and property-preserving network embedding methods, the network embedding methods with side information, and the advanced information preserving network embedding methods. Moreover, several evaluation approaches for network embedding and some useful online resources, including the network data sets and softwares, are reviewed, too. Finally, we discuss the framework of exploiting these network embedding methods to build an effective system and point out some potential future directions.
Using the notion of visibility representations, our paper establishes a new property of instances of the Nondeterministic Constraint Logic (NCL) problem (a PSPACE-complete problem that is very ...convenient to prove the PSPACE-hardness of reversible games with pushing blocks). Direct use of this property introduces an explosion in the number of gadgets needed to show PSPACE-hardness, but we show how to bring that number from 32 down to only three in the general case, and down to two in our specific case! We propose it as a step towards a broader and more general framework for studying games with irreversible gravity, and use this connection to guide an indirect polynomial-time many-one reduction from the NCL problem to the Hanano Puzzle—which is NP-hard—to prove it is PSPACE-complete.
•Resolves an open problem regarding the Hanano Puzzle that was posed in IPL.•Proposes a new framework to study games with irreversible gravity.•Previous approaches for such games relied on problem-specific tricks.•Provides a way to prove the hardness of such games with only 3 gadgets.
Let G and H be respectively a graph and a hypergraph defined on a same set of vertices, and let F be a fixed graph. We say that G F -overlays a hyperedge S of H if F is a spanning subgraph of the ...subgraph of G induced by S, and that it F -overlays H if it F -overlays every hyperedge of H. Motivated by structural biology, we study the computational complexity of two problems. The first problem, $(∆ ≤ k) F -$Overlay, consists in deciding whether there is a graph with maximum degree at most k that F -overlays a given hypergraph H. It is a particular case of the second problem Max $(∆ ≤ k) F -$Overlay, which takes a hypergraph H and an integer s as input, and consists in deciding whether there is a graph with maximum degree at most k that F -overlays at least s hyperedges of H.We give a complete polynomial/NP-complete dichotomy for the Max $(∆ ≤ k)-F -$Overlay prob-lems depending on the pairs (F, k), and establish the complexity of $(∆ ≤ k) F -$Overlay for many pairs (F, k).
Soit G et H respectivement un graphe et un hypergraphe défini sur un même ensemble de sommets, et F un graphe fixé. Nous disons que G F -couvre un hyperedge S de H si F est un sous-graphe couvrant du sous-graphe de G induit par S, et qu’il le F - couvre H si F recouvre chaque hyperedge de H. Motivés par la biologie structurale, nous étudions la complexité algorithmique de deux problèmes. Le premier problème, $(∆ ≤ k) F -$Overlay, consiste à décider s’il existe ou non un graphe avec un degré maximum égal à k qui F couvre un hypergraphe H. C’est un cas particulier du deuxième probléme Max $(∆ ≤ k) F -$Overlay, qui prend en entrée un hypergraphe H et un entier s, et consiste à décider s’il y a un graphe avec degré maximum d’au plus k que F -couvre au moins s hyperges de H. Nous donnons une dichotomie complète polynomiale/NP-complète pour les problemes Max $(∆ ≤ k)-F -$Overlay en fonction des paires (F, k), et la complexité de $(∆ ≤ k) F -$Overlay pour plusieurs paires (F, k).
The complexity of gradient descent: CLS = PPAD ∩ PLS Fearnley, John; Goldberg, Paul W.; Hollender, Alexandros ...
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing,
06/2021
Conference Proceeding
Recenzirano
Odprti dostop
We study search problems that can be solved by performing Gradient Descent on a bounded convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD ...and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain 0,12 is PPAD ∩ PLS-complete. This is the first natural problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) - which was defined by Daskalakis and Papadimitriou as a more “natural” counterpart to PPAD ∩ PLS and contains many interesting problems - is itself equal to PPAD ∩ PLS.
In this letter, we propose low-complexity linear equalizers for orthogonal time frequency space (OTFS) modulation that exploit the structure of the effective channel matrix in OTFS. The proposed ...approach exploits the block circulant nature of the OTFS channel matrix to achieve significant complexity reduction. For an N × M OTFS system, where N and M are the number of Doppler and delay bins, respectively, the proposed approach gives exact minimum mean square error (MMSE) and zero-forcing (ZF) solutions with just O(MN log MN) complexity, while MMSE and ZF solutions using the traditional matrix inversion approach require O(M 3 N 3 ) complexity. The proposed approach can provide low complexity initial solutions for local search techniques to achieve enhanced bit error performance.
This article introduces a novel scheme, termed coded compressed sensing, for unsourced multiple-access communication. The proposed divide-and-conquer approach leverages recent advances in compressed ...sensing and forward error correction to produce a novel uncoordinated access paradigm, along with a computationally efficient decoding algorithm. Within this framework, every active device partitions its data into several sub-blocks and, subsequently, adds redundancy using a systematic linear block code. Compressed sensing techniques are then employed to recover sub-blocks up to a permutation of their order, and the original messages are obtained by stitching fragments together using a tree-based algorithm. The error probability and computational complexity of this access paradigm are characterized. An optimization framework, which exploits the tradeoff between performance and computational complexity, is developed to assign parity-check bits to each sub-block. In addition, two emblematic parity bit allocation strategies are examined and their performances are analyzed in the limit as the number of active users and their corresponding payloads tend to infinity. The number of channel uses needed and the computational complexity associated with these allocation strategies are established for various scaling regimes. Numerical results demonstrate that coded compressed sensing outperforms other existing practical access strategies over a range of operational scenarios.
GMC: Graph-Based Multi-View Clustering Wang, Hao; Yang, Yan; Liu, Bing
IEEE transactions on knowledge and data engineering,
06/2020, Letnik:
32, Številka:
6
Journal Article
Recenzirano
Odprti dostop
Multi-view graph-based clustering aims to provide clustering solutions to multi-view data. However, most existing methods do not give sufficient consideration to weights of different views and ...require an additional clustering step to produce the final clusters. They also usually optimize their objectives based on fixed graph similarity matrices of all views. In this paper, we propose a general G raph-based M ulti-view C lustering (GMC) to tackle these problems. GMC takes the data graph matrices of all views and fuses them to generate a unified graph matrix. The unified graph matrix in turn improves the data graph matrix of each view, and also gives the final clusters directly. The key novelty of GMC is its learning method, which can help the learning of each view graph matrix and the learning of the unified graph matrix in a mutual reinforcement manner. A novel multi-view fusion technique can automatically weight each data graph matrix to derive the unified graph matrix. A rank constraint without introducing a tuning parameter is also imposed on the graph Laplacian matrix of the unified matrix, which helps partition the data points naturally into the required number of clusters. An alternating iterative optimization algorithm is presented to optimize the objective function. Experimental results using both toy data and real-world data demonstrate that the proposed method outperforms state-of-the-art baselines markedly.
Computing scattering resonances Ben-Artzi, Jonathan; Marletta, Marco; Rösler, Frank
Journal of the European Mathematical Society : JEMS,
2023, Letnik:
25, Številka:
9
Journal Article
PDF
