Let a polytope $\mathcal{P}$ be defined by one of the following ways: (i) $\mathcal{P} = \{x \in \mathbb{R}^n \colon A x \leq b\}$, where $A \in \mathbb{Z}^{(n+m) \times n}$, $b \in \mathbb{Z}^{(n+m)}$, and $rank(A) = n$, (ii) $\mathcal{P} = \{x \in \mathbb{R}_+^n \colon A x = b\}$, where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^{m}$, and $rank(A) = m$, and let all the rank minors of $A$ be bounded by $\Delta$ in the absolute values. We show that $|\mathcal{P} \cap \mathbb{Z}^n|$ can be computed with an algorithm, having the arithmetic complexity bound $$ O\bigl(d^{m + 4} \cdot \Delta^4 \cdot \log(\Delta) \bigr), $$ where $d = \dim(\mathcal{P})$, which outperforms the previous best known complexity bound $O(d^{m + O(1)} \cdot d^{\log_2(\Delta)})$. We do not directly compute the short rational generating function for $\mathcal{P} \cap \mathbb{Z}^n$, but compute its particular representation in the form of exponential series that depends on only one variable. The parametric versions of the above problem are also considered.
相關內容
We show that a relatively simple reasoning using von Neumann entropy inequalities yields a robust proof of the quantum Singleton bound for quantum error-correcting codes (QECC). For entanglement-assisted quantum error-correcting codes (EAQECC) and catalytic codes (CQECC), a type of generalized quantum Singleton bound [Brun et al., IEEE Trans. Inf. Theory 60(6):3073--3089 (2014)] was believed to hold for many years until recently one of us found a counterexample [MG, Phys. Rev. A 103, 020601 (2021)]. Here, we rectify this state of affairs by proving the correct generalized quantum Singleton bound, extending the above-mentioned proof method for QECC; we also prove information-theoretically tight bounds on the entanglement-communication tradeoff for EAQECC. All of the bounds relate block length $n$ and code length $k$ for given minimum distance $d$ and we show that they are robust, in the sense that they hold with small perturbations for codes which only correct most of the erasure errors of less than $d$ letters. In contrast to the classical case, the bounds take on qualitatively different forms depending on whether the minimum distance is smaller or larger than half the block length. We also provide a propagation rule: any pure QECC yields an EAQECC with the same distance and dimension, but of shorter block length.
We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on $H$-minor free graphs. In particular, we obtain the following results (where $k$ is the solution-size parameter). 1. $2^{O(\sqrt{k}\log k)} \cdot n^{O(1)}$ time algorithms for Edge Bipartization and Odd Cycle Transversal; 2. a $2^{O(\sqrt{k}\log^4 k)} \cdot n^{O(1)}$ time algorithm for Edge Multiway Cut and a $2^{O(r \sqrt{k} \log k)} \cdot n^{O(1)}$ time algorithm for Vertex Multiway Cut, where $r$ is the number of terminals to be separated; 3. a $2^{O((r+\sqrt{k})\log^4 (rk))} \cdot n^{O(1)}$ time algorithm for Edge Multicut and a $2^{O((\sqrt{rk}+r) \log (rk))} \cdot n^{O(1)}$ time algorithm for Vertex Multicut, where $r$ is the number of terminal pairs to be separated; 4. a $2^{O(\sqrt{k} \log g \log^4 k)} \cdot n^{O(1)}$ time algorithm for Group Feedback Edge Set and a $2^{O(g \sqrt{k}\log(gk))} \cdot n^{O(1)}$ time algorithm for Group Feedback Vertex Set, where $g$ is the size of the group. 5. In addition, our approach also gives $n^{O(\sqrt{k})}$ time algorithms for all above problems with the exception of $n^{O(r+\sqrt{k})}$ time for Edge/Vertex Multicut and $(ng)^{O(\sqrt{k})}$ time for Group Feedback Edge/Vertex Set. We obtain our results by giving a new decomposition theorem on graphs of bounded genus, or more generally, an $h$-almost-embeddable graph for any fixed constant $h$. In particular we show the following. Let $G$ be an $h$-almost-embeddable graph for a constant $h$. Then for every $p\in\mathbb{N}$, there exist disjoint sets $Z_1,\dots,Z_p \subseteq V(G)$ such that for every $i \in \{1,\dots,p\}$ and every $Z'\subseteq Z_i$, the treewidth of $G/(Z_i\backslash Z')$ is $O(p+|Z'|)$. Here $G/(Z_i\backslash Z')$ is the graph obtained from $G$ by contracting edges with both endpoints in $Z_i \backslash Z'$.
We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant, which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: (1) Computing $\sum_S\det({\bf A}_{S,S})^p$ exactly for every (fixed) positive even integer $p$ is UP-hard and Mod$_3$P-hard, which gives a negative answer to an open question posed by Kulesza and Taskar. (2) $\sum_S\det({\bf A}_{S,S})\det({\bf B}_{S,S})\det({\bf C}_{S,S})$ is NP-hard to approximate within a factor of $2^{O(|I|^{1-\epsilon})}$ or $2^{O(n^{1/\epsilon})}$ for any $\epsilon>0$, where $|I|$ is the input size and $n$ is the order of the input matrix. This result is stronger than the #P-hardness for the case of two matrices derived by Gillenwater. (3) There exists a $k^{O(k)}n^{O(1)}$-time algorithm for computing $\sum_S\det({\bf A}_{S,S})\det({\bf B}_{S,S})$, where $k$ is the maximum rank of $\bf A$ and $\bf B$ or the treewidth of the graph formed by nonzero entries of $\bf A$ and $\bf B$. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix $\bf A$ of treewidth $w$: (4) We can compute a $2^{\frac{n}{2p-1}}$-approximation to $\sum_S\det({\bf A}_{S,S})^p$ for any fractional number $p>1$ in $w^{O(wp)}n^{O(1)}$ time. (5) We can find a $2^{\sqrt n}$-approximation to unconstrained MAP inference in $w^{O(w\sqrt n)}n^{O(1)}$ time.
Escaping saddle points is a central research topic in nonconvex optimization. In this paper, we propose a simple gradient-based algorithm such that for a smooth function $f\colon\mathbb{R}^n\to\mathbb{R}$, it outputs an $\epsilon$-approximate second-order stationary point in $\tilde{O}(\log n/\epsilon^{1.75})$ iterations. Compared to the previous state-of-the-art algorithms by Jin et al. with $\tilde{O}((\log n)^{4}/\epsilon^{2})$ or $\tilde{O}((\log n)^{6}/\epsilon^{1.75})$ iterations, our algorithm is polynomially better in terms of $\log n$ and matches their complexities in terms of $1/\epsilon$. For the stochastic setting, our algorithm outputs an $\epsilon$-approximate second-order stationary point in $\tilde{O}((\log n)^{2}/\epsilon^{4})$ iterations. Technically, our main contribution is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve the polynomial speedup in $\log n$ compared to the perturbed gradient descent methods. Finally, we also perform numerical experiments that support our results.
Given a simple graph $G$ and an integer $k$, the goal of $k$-Clique problem is to decide if $G$ contains a complete subgraph of size $k$. We say an algorithm approximates $k$-Clique within a factor $g(k)$ if it can find a clique of size at least $k / g(k)$ when $G$ is guaranteed to have a $k$-clique. Recently, it was shown that approximating $k$-Clique within a constant factor is W[1]-hard [Lin21]. We study the approximation of $k$-Clique under the Exponential Time Hypothesis (ETH). The reduction of [Lin21] already implies an $n^{\Omega(\sqrt[6]{\log k})}$-time lower bound under ETH. We improve this lower bound to $n^{\Omega(\log k)}$. Using the gap-amplification technique by expander graphs, we also prove that there is no $k^{o(1)}$ factor FPT-approximation algorithm for $k$-Clique under ETH. We also suggest a new way to prove the Parameterized Inapproximability Hypothesis (PIH) under ETH. We show that if there is no $n^{O(\frac{k}{\log k})}$ algorithm to approximate $k$-Clique within a constant factor, then PIH is true.
It is well known [Lov\'{a}sz, 1967] that up to isomorphism a graph $G$ is determined by the homomorphism counts $\hom(F, G)$, i.e., the number of homomorphisms from $F$ to $G$, where $F$ ranges over all graphs. Moreover, it suffices that $F$ ranges over the graphs with at most as many vertices as $G$. Thus in principle we can answer any query concerning $G$ with only accessing the $\hom(\cdot,G)$'s instead of $G$ itself. In this paper, we zoom in on those queries that can be answered using a constant number of $\hom(\cdot,G)$ for every graph $G$. We observe that if a query $\varphi$ is expressible as a Boolean combination of universal sentences in first-order logic, then whether a graph $G$ satisfies $\varphi$ can be determined by the vector \[\overrightarrow{\mathrm{hom}}_{F_1, \ldots, F_k}(G):= \big(\mathrm{hom}(F_1, G), \ldots, \mathrm{hom}(F_k, G)\big),\] where the graphs $F_1,\ldots,F_k$ only depend on $\varphi$. This leads to a query algorithm for $\varphi$ that is non-adaptive in the sense that those $F_i$ are independent of the input $G$. On the other hand, we prove that the existence of an isolated vertex, which is not definable by such a $\varphi$ but in first-order logic, cannot be determined by any $\overrightarrow{\mathrm{hom}}_{F_1, \ldots, F_k}(\cdot)$. These results provide a clear delineation of the power of non-adaptive query algorithms with access to a constant number of $\hom(\cdot, G)$'s. For adaptive query algorithms, i.e., algorithms that might access some $\hom(F_{i+1}, G)$ with $F_{i+1}$ depending on $\hom(F_1, G), \ldots, \hom(F_i, G)$, we show that three homomorphism counts $\hom(\cdot,G)$ are both sufficient and in general necessary to determine the graph $G$. In particular, by three adaptive queries we can answer any question on $G$. Moreover, adaptively accessing two $\hom(\cdot, G)$'s is already enough to detect an isolated vertex.
A family of closed simple (i.e., Jordan) curves is $m$-intersecting if any pair of its curves have at most $m$ points of common intersection. We say that a pair of such curves touch if they intersect at a single point of common tangency. In this work we show that any $m$-intersecting family of $n$ Jordan curves in general position in the plane contains $O\left(n^{2-\frac{1}{3m+15}}\right)$ touching pairs Furthermore, we use the string separator theorem of Fox and Pach in order to establish the following Crossing Lemma for contact graphs of Jordan curves: Let $\Gamma$ be an $m$-intersecting family of closed Jordan curves in general position in the plane with exactly $T=\Omega(n)$ touching pairs of curves, then the curves of $\Gamma$ determine $\Omega\left(T\cdot\left(\frac{T}{n}\right)^{\frac{1}{9m+45}}\right)$ intersection points. This extends the similar bounds that were previously established by Salazar for the special case of pairwise intersecting (and $m$-intersecting) curves. Specializing to the case at hand, this substantially improves the bounds that were recently derived by Pach, Rubin and Tardos for arbitrary families of Jordan curves.
In this work we consider the well-known Secretary Problem -- a number $n$ of elements, each having an adversarial value, are arriving one-by-one according to some random order, and the goal is to choose the highest value element. The decisions are made online and are irrevocable -- if the algorithm decides to choose or not to choose the currently seen element, based on the previously observed values, it cannot change its decision later regarding this element. The measure of success is the probability of selecting the highest value element, minimized over all adversarial assignments of values. We show existential and constructive upper bounds on approximation of the success probability in this problem, depending on the entropy of the randomly chosen arrival order, including the lowest possible entropy $O(\log\log (n))$ for which the probability of success could be constant. We show that below entropy level $\mathcal{H}<0.5\log\log n$, all algorithms succeed with probability $0$ if random order is selected uniformly at random from some subset of permutations, while we are able to construct in polynomial time a non-uniform distribution with entropy $\mathcal{H}$ resulting in success probability of at least $\Omega\left(\frac{1}{(\log\log n +3\log\log\log n -\mathcal{H})^{2+\epsilon}}\right)$, for any constant $\epsilon>0$. We also prove that no algorithm using entropy $\mathcal{H}=O((\log\log n)^a)$ can improve our result by more than polynomially, for any constant $0<a<1$. For entropy $\log\log (n)$ and larger, our analysis precisely quantifies both multiplicative and additive approximation of the success probability. In particular, we improve more than doubly exponentially on the best previously known additive approximation guarantee for the secretary problem.
This paper deals with the modular irregularity strength of a graph of n vertices, a new graph invariant, modified from the irregularity strength, by changing the condition of the vertex-weight set associate to the well-known irregular labeling from n distinct positive integer to Z_n-the group of integer modulo n. Investigating the triangular book graph B_m^((3)), we first find the irregularity strength of triangular book graph s(B_m^((3)) ), as the lower bound for the modular irregularity strength, and then construct a modular irregular s(B_m^((3)) )-labeling. The result shows that triangular book graphs admit a modular irregular labeling and its modular irregularity strength and irregularity strength are equal, except for a small case and the infinity property.
This work considers the problem of provably optimal reinforcement learning for episodic finite horizon MDPs, i.e. how an agent learns to maximize his/her long term reward in an uncertain environment. The main contribution is in providing a novel algorithm --- Variance-reduced Upper Confidence Q-learning (vUCQ) --- which enjoys a regret bound of $\widetilde{O}(\sqrt{HSAT} + H^5SA)$, where the $T$ is the number of time steps the agent acts in the MDP, $S$ is the number of states, $A$ is the number of actions, and $H$ is the (episodic) horizon time. This is the first regret bound that is both sub-linear in the model size and asymptotically optimal. The algorithm is sub-linear in that the time to achieve $\epsilon$-average regret for any constant $\epsilon$ is $O(SA)$, which is a number of samples that is far less than that required to learn any non-trivial estimate of the transition model (the transition model is specified by $O(S^2A)$ parameters). The importance of sub-linear algorithms is largely the motivation for algorithms such as $Q$-learning and other "model free" approaches. vUCQ algorithm also enjoys minimax optimal regret in the long run, matching the $\Omega(\sqrt{HSAT})$ lower bound. Variance-reduced Upper Confidence Q-learning (vUCQ) is a successive refinement method in which the algorithm reduces the variance in $Q$-value estimates and couples this estimation scheme with an upper confidence based algorithm. Technically, the coupling of both of these techniques is what leads to the algorithm enjoying both the sub-linear regret property and the asymptotically optimal regret.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191