亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

We study a variant of the subgraph isomorphism problem that is of high interest to the quantum computing community. Our results give an algorithm to perform pattern matching in quantum circuits for many patterns simultaneously, independently of the number of patterns. After a pre-computation step in which the patterns are compiled into a decision tree, the running time is linear in the size of the input quantum circuit. More generally, we consider connected port graphs, in which every edge $e$ incident to $v$ has a label $L_v(e)$ unique in $v$. Jiang and Bunke showed that the subgraph isomorphism problem $H \subseteq G$ for such graphs can be solved in time $O(|V(G)| \cdot |V(H)|)$. We show that if in addition the graphs are directed acyclic, then the subgraph isomorphism problem can be solved for an unbounded number of patterns simultaneously. We enumerate all $m$ pattern matches in time $O(P)^{P+3/2} \cdot |V(G)| + O(m)$, where $P$ is the number of vertices of the largest pattern. In the case of quantum circuits, we can express the bound obtained in terms of the maximum number of qubits $N$ and depth $\delta$ of the patterns : $O(N)^{N + 1/2} \cdot \delta \log \delta \cdot |V(G)| + O(m)$.

The inverse problem of recovery of a potential on a quantum tree graph from Weyl's matrix given at a number of points is considered. A method for its numerical solution is proposed. The overall approach is based on the leaf peeling method combined with Neumann series of Bessel functions (NSBF) representations for solutions of Sturm-Liouville equations. In each step, the solution of the arising inverse problems reduces to dealing with the NSBF coefficients. The leaf peeling method allows one to localize the general inverse problem to local problems on sheaves, while the approach based on the NSBF representations leads to splitting the local problems into two-spectra inverse problems on separate edges and reduce them to systems of linear algebraic equations for the NSBF coefficients. Moreover, the potential on each edge is recovered from the very first NSBF coefficient. The proposed method leads to an efficient numerical algorithm that is illustrated by numerical tests.

We study the spectral implications of re-weighting a graph by the $\ell_\infty$-Lewis weights of its edges. Our main motivation is the ER-Minimization problem (Saberi et al., SIAM'08): Given an undirected graph $G$, the goal is to find positive normalized edge-weights $w\in \mathbb{R}_+^m$ which minimize the sum of pairwise \emph{effective-resistances} of $G_w$ (Kirchhoff's index). By contrast, $\ell_\infty$-Lewis weights minimize the \emph{maximum} effective-resistance of \emph{edges}, but are much cheaper to approximate, especially for Laplacians. With this algorithmic motivation, we study the ER-approximation ratio obtained by Lewis weights. Our first main result is that $\ell_\infty$-Lewis weights provide a constant ($\approx 3.12$) approximation for ER-minimization on \emph{trees}. The proof introduces a new technique, a local polarization process for effective-resistances ($\ell_2$-congestion) on trees, which is of independent interest in electrical network analysis. For general graphs, we prove an upper bound $\alpha(G)$ on the approximation ratio obtained by Lewis weights, which is always $\leq \min\{ \text{diam}(G), \kappa(L_{w_\infty})\}$, where $\kappa$ is the condition number of the weighted Laplacian. All our approximation algorithms run in \emph{input-sparsity} time $\tilde{O}(m)$, a major improvement over Saberi et al.'s $O(m^{3.5})$ SDP for exact ER-minimization. Finally, we demonstrate the favorable effects of $\ell_\infty$-LW reweighting on the \emph{spectral-gap} of graphs and on their \emph{spectral-thinness} (Anari and Gharan, 2015). En-route to our results, we prove a weighted analogue of Mohar's classical bound on $\lambda_2(G)$, and provide a new characterization of leverage-scores of a matrix, as the gradient (w.r.t weights) of the volume of the enclosing ellipsoid.

This paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (LICS 2022) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs: an objective is positional if and only if it admits well-ordered monotone universal graphs. We extend Ohlmann's characterisation to encompass (finite or infinite) memory upper bounds. We prove that objectives admitting optimal strategies with $\varepsilon$-memory less than $m$ (a memory that cannot be updated when reading an $\varepsilon$-edge) are exactly those which admit well-founded monotone universal graphs whose antichains have size bounded by $m$. We also give a characterisation of chromatic memory by means of appropriate universal structures. Our results apply to finite as well as infinite memory bounds (for instance, to objectives with finite but unbounded memory, or with countable memory strategies). We illustrate the applicability of our framework by carrying out a few case studies, we provide examples witnessing limitations of our approach, and we discuss general closure properties which follow from our results.

NISQ devices have several physical limitations and unavoidable noisy quantum operations, and only small circuits can be executed on a quantum machine to get reliable results. This leads to the quantum hardware under-utilization issue. Here, we address this problem and improve the quantum hardware throughput by proposing a Quantum Multi-programming Compiler (QuMC) to execute multiple quantum circuits on quantum hardware simultaneously. This approach can also reduce the total runtime of circuits. We first introduce a parallelism manager to select an appropriate number of circuits to be executed at the same time. Second, we present two different qubit partitioning algorithms to allocate reliable partitions to multiple circuits - a greedy and a heuristic. Third, we use the Simultaneous Randomized Benchmarking protocol to characterize the crosstalk properties and consider them in the qubit partition process to avoid the crosstalk effect during simultaneous executions. Finally, we enhance the mapping transition algorithm to make circuits executable on hardware using a decreased number of inserted gates. We demonstrate the performance of our QuMC approach by executing circuits of different sizes on IBM quantum hardware simultaneously. We also investigate this method on VQE algorithm to reduce its overhead.

Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions must be interviewed or made offers to. There is a finite time budget for interviewing or making offers, and a stochastic realization after each decision, leading to computationally-challenging problems. In the first problem, we study sequential interviewing and show that a computationally-tractable, non-adaptive policy that must make offers immediately after interviewing is approximately optimal, assuming offerees always accept their offers. In the second problem, we assume that applicants have already been interviewed but only accept offers with some probability; we develop a computationally-tractable policy that makes offers for the different positions in parallel, which can be used even if positions are heterogeneous and is approximately optimal relative to a policy that can make the same amount of offers not in parallel. In the third problem, we introduce a model where the hiring firm is tightly time constrained and must send all offers simultaneously in a single time step, with the possibility of hiring over capacity at a cost; we provide nearly-tight bounds for the performance of practically motivated value-ordered policies. All in all, our paper takes a unified approach to three different hiring problems, based on linear programming. Our results in the first two problems generalize and improve the guarantees from Purohit et al. (2019) that were between 1/8 and 1/2 to new guarantees that are at least 1-1/e. We also numerically compare three different settings of making offers to candidates (sequentially, in parallel, or simultaneously), providing insight on when a firm should favor each one.

Choiceless Polynomial Time (CPT) is one of the few remaining candidate logics for capturing PTIME. In this paper, we make progress towards separating CPT from polynomial time by firstly establishing a connection between the expressive power of CPT and the existence of certain symmetric circuit families, and secondly, proving lower bounds against these circuits. We focus on the isomorphism problem of unordered Cai-F\"urer-Immerman-graphs (the CFI-query) as a potential candidate for separating CPT from P. Results by Dawar, Richerby and Rossman, and subsequently by Pakusa, Schalth\"ofer and Selman show that the CFI-query is CPT-definable on linearly ordered and preordered base graphs with small colour classes. We define a class of CPT-algorithms, that we call "CFI-symmetric algorithms", which generalises all the known ones, and show that such algorithms can only define the CFI-query on a given class of base graphs if there exists a family of symmetric XOR-circuits with certain properties. These properties include that the circuits have the same symmetries as the base graphs, are of polynomial size, and satisfy certain fan-in restrictions. Then we prove that such circuits with slightly strengthened requirements (i.e. stronger symmetry and fan-in and fan-out restrictions) do not exist for the n-dimensional hypercubes as base graphs. This almost separates the CFI-symmetric algorithms from polynomial time - up to the gap that remains between the circuits whose existence we can currently disprove and the circuits whose existence is necessary for the definability of the CFI-query by a CFI-symmetric algorithm.

The inductive biases of graph representation learning algorithms are often encoded in the background geometry of their embedding space. In this paper, we show that general directed graphs can be effectively represented by an embedding model that combines three components: a pseudo-Riemannian metric structure, a non-trivial global topology, and a unique likelihood function that explicitly incorporates a preferred direction in embedding space. We demonstrate the representational capabilities of this method by applying it to the task of link prediction on a series of synthetic and real directed graphs from natural language applications and biology. In particular, we show that low-dimensional cylindrical Minkowski and anti-de Sitter spacetimes can produce equal or better graph representations than curved Riemannian manifolds of higher dimensions.

Reasoning with knowledge expressed in natural language and Knowledge Bases (KBs) is a major challenge for Artificial Intelligence, with applications in machine reading, dialogue, and question answering. General neural architectures that jointly learn representations and transformations of text are very data-inefficient, and it is hard to analyse their reasoning process. These issues are addressed by end-to-end differentiable reasoning systems such as Neural Theorem Provers (NTPs), although they can only be used with small-scale symbolic KBs. In this paper we first propose Greedy NTPs (GNTPs), an extension to NTPs addressing their complexity and scalability limitations, thus making them applicable to real-world datasets. This result is achieved by dynamically constructing the computation graph of NTPs and including only the most promising proof paths during inference, thus obtaining orders of magnitude more efficient models. Then, we propose a novel approach for jointly reasoning over KBs and textual mentions, by embedding logic facts and natural language sentences in a shared embedding space. We show that GNTPs perform on par with NTPs at a fraction of their cost while achieving competitive link prediction results on large datasets, providing explanations for predictions, and inducing interpretable models. Source code, datasets, and supplementary material are available online at //github.com/uclnlp/gntp.

Dynamic programming (DP) solves a variety of structured combinatorial problems by iteratively breaking them down into smaller subproblems. In spite of their versatility, DP algorithms are usually non-differentiable, which hampers their use as a layer in neural networks trained by backpropagation. To address this issue, we propose to smooth the max operator in the dynamic programming recursion, using a strongly convex regularizer. This allows to relax both the optimal value and solution of the original combinatorial problem, and turns a broad class of DP algorithms into differentiable operators. Theoretically, we provide a new probabilistic perspective on backpropagating through these DP operators, and relate them to inference in graphical models. We derive two particular instantiations of our framework, a smoothed Viterbi algorithm for sequence prediction and a smoothed DTW algorithm for time-series alignment. We showcase these instantiations on two structured prediction tasks and on structured and sparse attention for neural machine translation.