Attention And Positional Encoding Are (Almost) All You Need For Shape Matching

The fast development of novel approaches derived from the Transformers architecture has led to outstanding performance in different scenarios, from Natural Language Processing to Computer Vision. Recently, they achieved impressive results even in the challenging task of non-rigid shape matching. However, little is known about the capability of the Transformer-encoder architecture for the shape matching task, and its performances still remained largely unexplored. In this paper, we step back and investigate the contribution made by the Transformer-encoder architecture compared to its more recent alternatives, focusing on why and how it works on this specific task. Thanks to the versatility of our implementation, we can harness the bi-directional structure of the correspondence problem, making it more interpretable. Furthermore, we prove that positional encodings are essential for processing unordered point clouds. Through a comprehensive set of experiments, we find that attention and positional encoding are (almost) all you need for shape matching. The simple Transformer-encoder architecture, coupled with relative position encoding in the attention mechanism, is able to obtain strong improvements, reaching the current state-of-the-art.     

All Things Are Connected

For any field to move ahead, researchers must try things even when they don't quite know what they're doing.     

Maximum Matching in Regular and Almost Regular Graphs

We present an O(n ²logn)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(rn ²logn) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in $O(\sqrt{n}m)$ -time for graphs with m edges, whenever m=ω(rn ^1.5logn).     

Easy Generation of Facial Animation Using Motion Graphs

Facial animation is a time‐consuming and cumbersome task that requires years of experience and/or a complex and expensive set‐up. This becomes an issue, especially when animating the multitude of secondary characters required, e.g. in films or video‐games. We address this problem with a novel technique that relies on motion graphs to represent a landmarked database. Separate graphs are created for different facial regions, allowing a reduced memory footprint compared to the original data. The common poses are identified using a Euclidean‐based similarity metric and merged into the same node. This process traditionally requires a manually chosen threshold, however, we simplify it by optimizing for the desired graph compression. Motion synthesis occurs by traversing the graph using Dijkstra's algorithm, and coherent noise is introduced by swapping some path nodes with their neighbours. Expression labels, extracted from the database, provide the control mechanism for animation. We present a way of creating facial animation with reduced input that automatically controls timing and pose detail. Our technique easily fits within video‐game and crowd animation contexts, allowing the characters to be more expressive with less effort. Furthermore, it provides a starting point for content creators aiming to bring more life into their characters.     

为什么人机界面无处不在

显示器、触摸屏、终端一这些人机界面似乎无处不在。它们中的很多比二十年前的按钮和开关还要小,而且功能已经非常复杂,可以帮助管理和运营进行控制,并为其提供信息。     

非凡影像皆可能——2010北京万星EPSON高端投影机演示会成功举办

以“‘清’舞神州,亮‘彩’世界”为主题的2010北京万星EPSON高端投影机演示会在北京举办。北京万星富视科技有限公司携手爱普生（中国）公司将爱普生工程投影机担纲主角的高清投影解决方案向众多与会者进行了展示与讲解。在演示会上与会者对3D显示、无缝拼接、全息投影等一系列代表目前最新高清应用的解决方案有了清晰地体验与了解,进一步加深了对爱普生EB—Z8000WU、EB—Z8050W等高端工程机的印象与感受。     

非凡影像皆可能——2010北京万星EPSON高端投影机演示会成功举办

以‘清'舞神州,亮‘彩'世界为主题的2010北京万星EPSON高端投影机演示会在北京举办。北京万星富视科技有限公司携手爱普生(中国)公司将爱普生工程投影机担纲主角的高清投影解决方案向众多与会者进行了展示与讲解。在演示会上与会者对3D显示、无缝拼接、全息投影等一系列     

Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)

We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrix games, where each player’s payoffs are bounded and independent random variables, not necessarily identically distributed, but with almost common expectations. We show that the completely mixed uniform strategy profile, i.e., the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is with high probability a $\sqrt{\frac{\ln n}{n}}$ -Nash equilibrium and a $\sqrt{\frac{3\ln n}{n}}$ -well supported Nash equilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nash equilibrium for random bimatrix games, since it is, with high probability, an ?-well-supported Nash equilibrium where ? tends to zero as n tends to infinity.     

Scheduling Parallel Task Graphs on (Almost) Homogeneous Multicluster Platforms

Applications structured as parallel task graphs exhibit both data and task parallelism and arise in many domains. Scheduling these applications efficiently on parallel platforms has been a long-standing challenge. In the case of a single homogeneous platform, such as a cluster, results have been obtained both in theory, i.e., guaranteed algorithms, and, in practice, i.e., pragmatic heuristics. Due to task parallelism, these applications are well suited for execution on distributed platforms that span multiple clusters possibly in multiple institutions. However, the only available results in this context are nonguaranteed heuristics. In this paper, we develop a scheduling algorithm, MCGAS, which is applicable to multicluster platforms that are almost homogeneous. Such platforms are often found as large subsets of multicluster platforms. Our novel contribution is that MCGAS computes task allocations so that a (tunable) performance guarantee is provided. Since a performance guarantee does not necessarily imply good average performance in practice, we also compare MCGAS with a recently proposed nonguaranteed algorithm. Using simulation over a wide range of experimental scenarios, we find that MCGAS leads to better average application makespans than its competitor.     

Where Are All the Intelligent Agents?

There has been much research and talk about intelligent agents, but few real-world implementations.     

Matching Algorithms Are Fast in Sparse Random Graphs

We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every non-maximum matching has an augmenting path of length O(log n). This implies that augmenting path algorithms like the Hopcroft-Karp algorithm for bipartite graphs and the Micali-Vazirani algorithm for general graphs, which have a worst case running time of O(m√n), run in time O(m log n) with high probability, where m is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least ln (n) [Average Case Analysis of Algorithms for Matchings and Related Problems, Journal of the ACM, 41(6):1329-1356, 1994]. Our results hold if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani.     

Quantum Query Complexity of Almost All Functions with Fixed On-set Size

This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\)-variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\), where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N}\right)}\) for a constant \({c > 0}\). This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\): \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N}\right)}\). In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor.     

The Agents Are All Busy Doing Stuff!

In answer to the question, "Where have all the agents gone?" this column asserts that agent technologies are pervasive, not missing.     

All Pairs Shortest Distances for Graphs with Small Integer Length Edges

There is a way to transform the All Pairs Shortest Distances (APSD) problem where the edge lengths are integers with small (?M) absolute value into a problem with edge lengths in {−1, 0, 1}. This transformation allows us to use the algorithms we developed earlier ([1]) and yields quite efficient algorithms. In this paper we give new improved algorithms for these problems. Forn=|V| the number of vertices,Mthe bound on edge length, andωthe exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSD(n, M) algorithm which runs inO(T(n, M)) time, where[formula]2. A undirected APSD(n, M) algorithm which runs inO(M^(ω+1)/2n^ωlog(Mn)) time.     

An Efficient Algorithm for Finding All Hinge Vertices on Trapezoid Graphs

The distance between at least two vertices becomes longer after the removal of a hinge vertex. Thus a faulty hinge vertex will increase the overall communication cost in a network. Therefore, finding the set of all hinge vertices in a graph can be used to identify critical nodes in a real network. An O(n log n) time algorithm has been proposed here to find all hinge vertices of a trapezoid graph with n vertices.     

A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs

In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O (n+m+ τ n) time where the given graph has n vertices, m edges, and τ spanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal. Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible. If we employ the depth-first search rule, we can save the memory requirement to O (n+m). A breadth-first implementation requires as much as O (m+ τ n) space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requires O (n+ m + τ n) time and O (m+ τ n) space when we have a minimum spanning tree. Received January 21, 1995; revised February 19, 1996.     

首台开放式办公平台的彩色多功能一体机——专访富士施乐(中国)有限公司产品经理郭峰

APC7550I是富士施乐去年推出的首台基于开放式办公平台的彩色数码多功能一体机.其倡导的彩色办公和开放式办公已经在市场上获得普遍认同.希望能够借助OA杂志社的机会使读者对这台机器本身和其倡导的开放式办公的各种功能有更深入的了解.……