The {\em discrepancy} of a matrix $M \in \mathbb{R}^{d \times n}$ is given by $\mathrm{DISC}(M) := \min_{\boldsymbol{x} \in \{-1,1\}^n} \|M\boldsymbol{x}\|_\infty$. An outstanding conjecture, attributed to Koml\'os, stipulates that $\mathrm{DISC}(M) = O(1)$, whenever $M$ is a Koml\'os matrix, that is, whenever every column of $M$ lies within the unit sphere. Our main result asserts that $\mathrm{DISC}(M + R/\sqrt{d}) = O(d^{-1/2})$ holds asymptotically almost surely, whenever $M \in \mathbb{R}^{d \times n}$ is Koml\'os, $R \in \mathbb{R}^{d \times n}$ is a Rademacher random matrix, $d = \omega(1)$, and $n = \tilde \omega(d^{5/4})$. We conjecture that $n = \omega(d \log d)$ suffices for the same assertion to hold. The factor $d^{-1/2}$ normalising $R$ is essentially best possible and the dependency between $n$ and $d$ is also asymptotically best possible.
相關內容
We prove the following variant of Levi's Enlargement Lemma: for an arbitrary arrangement $\mathcal{A}$ of $x$-monotone pseudosegments in the plane and a pair of points $a,b$ with distinct $x$-coordinates and not on the same pseudosegment, there exists a simple $x$-monotone curve with endpoints $a,b$ that intersects every curve of $\mathcal{A}$ at most once. As a consequence, every simple monotone drawing of a graph can be extended to a simple monotone drawing of a complete graph. We also show that extending an arrangement of cylindrically monotone pseudosegments is not always possible; in fact, the corresponding decision problem is NP-hard.
The Bimatrix Nash Equilibrium (NE) for $m \times n$ real matrices $R$ and $C$, denoted as the {\it Row} and {\it Column} players, is characterized as follows: Let $\Delta =S_m \times S_n$, where $S_k$ denotes the unit simplex in $\mathbb{R}^k$. For a given point $p=(x,y) \in \Delta$, define $R[p]=x^TRy$ and $C[p]=x^TCy$. Consequently, there exists a subset $\Delta_* \subset \Delta$ such that for any $p_*=(x_*,y_*) \in \Delta_*$, $\max_{p \in \Delta, y=y_*}R[p]=R[p_*]$ and $\max_{p \in \Delta, x=x_* } C[p]=C[p_*]$. The computational complexity of bimatrix NE falls within the class of {\it PPAD-complete}. Although the von Neumann Minimax Theorem is a special case of bimatrix NE, we introduce a novel extension termed {\it Trilinear Minimax Relaxation} (TMR) with the following implications: Let $\lambda^*=\min_{\alpha \in S_{2}} \max_{p \in \Delta} (\alpha_1 R[p]+ \alpha_2C[p])$ and $\lambda_*=\max_{p \in \Delta} \min_{\alpha \in S_{2}} (\alpha_1 R[p]+ \alpha_2C[p])$. $\lambda^* \geq \lambda_*$. $\lambda^*$ is computable as a linear programming in $O(mn)$ time, ensuring $\max_{p_* \in \Delta_*}\min \{R[p_*], C[p_*]\} \leq \lambda^*$, meaning that in any Nash Equilibrium it is not possible to have both players' payoffs to exceed $\lambda^*$. $\lambda^*=\lambda_*$ if and only if there exists $p^* \in \Delta$ such that $\lambda^*= \min\{R[p^*], C[p^*]\}$. Such a $p^*$ serves as an approximate Nash Equilibrium. We analyze the cases where such $p^*$ exists and is computable. Even when $\lambda^* > \lambda_*$, we derive approximate Nash Equilibria. In summary, the aforementioned properties of TMR and its efficient computational aspects underscore its significance and relevance for Nash Equilibrium, irrespective of the computational complexity associated with bimatrix Nash Equilibrium. Finally, we extend TMR to scenarios involving three or more players.
This paper deals with a Skorokhod's integral based least squares type estimator $\widehat\theta_N$ of the drift parameter $\theta_0$ computed from $N\in\mathbb N^*$ (possibly dependent) copies $X^1,\dots,X^N$ of the solution $X$ of $dX_t =\theta_0b(X_t)dt +\sigma dB_t$, where $B$ is a fractional Brownian motion of Hurst index $H\in (1/3,1)$. On the one hand, some convergence results are established on $\widehat\theta_N$ when $H = 1/2$. On the other hand, when $H\neq 1/2$, Skorokhod's integral based estimators as $\widehat\theta_N$ cannot be computed from data, but in this paper some convergence results are established on a computable approximation of $\widehat\theta_N$.
Duan, Wu and Zhou (FOCS 2023) recently obtained the improved upper bound on the exponent of square matrix multiplication $\omega<2.3719$ by introducing a new approach to quantify and compensate the ``combination loss" in prior analyses of powers of the Coppersmith-Winograd tensor. In this paper we show how to use this new approach to improve the exponent of rectangular matrix multiplication as well. Our main technical contribution is showing how to combine this analysis of the combination loss and the analysis of the fourth power of the Coppersmith-Winograd tensor in the context of rectangular matrix multiplication developed by Le Gall and Urrutia (SODA 2018).
We find a succinct expression for computing the sequence $x_t = a_t x_{t-1} + b_t$ in parallel with two prefix sums, given $t = (1, 2, \dots, n)$, $a_t \in \mathbb{R}^n$, $b_t \in \mathbb{R}^n$, and initial value $x_0 \in \mathbb{R}$. On $n$ parallel processors, the computation of $n$ elements incurs $\mathcal{O}(\log n)$ time and $\mathcal{O}(n)$ space. Sequences of this form are ubiquitous in science and engineering, making efficient parallelization useful for a vast number of applications. We implement our expression in software, test it on parallel hardware, and verify that it executes faster than sequential computation by a factor of $\frac{n}{\log n}$.
We define rewinding operators that invert quantum measurements. Then, we define complexity classes ${\sf RwBQP}$, ${\sf CBQP}$, and ${\sf AdPostBQP}$ as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that ${\sf BPP}^{\sf PP}\subseteq{\sf RwBQP}={\sf CBQP}={\sf AdPostBQP}\subseteq{\sf PSPACE}$. As a byproduct of this result, we show that any problem in ${\sf PostBQP}$ can be solved with only postselections of outputs whose probabilities are polynomially close to one. Under the strongly believed assumption that ${\sf BQP}\nsupseteq{\sf SZK}$, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. In addition, we consider rewindable Clifford and instantaneous quantum polynomial time circuits.
Join-preserving maps on the discrete time scale $\omega^+$, referred to as time warps, have been proposed as graded modalities that can be used to quantify the growth of information in the course of program execution. The set of time warps forms a simple distributive involutive residuated lattice -- called the time warp algebra -- that is equipped with residual operations relevant to potential applications. In this paper, we show that although the time warp algebra generates a variety that lacks the finite model property, it nevertheless has a decidable equational theory. We also describe an implementation of a procedure for deciding equations in this algebra, written in the OCaml programming language, that makes use of the Z3 theorem prover.
Secure multiparty computation (MPC) schemes allow two or more parties to conjointly compute a function on their private input sets while revealing nothing but the output. Existing state-of-the-art number-theoretic-based designs face the threat of attacks through quantum algorithms. In this context, we present secure MPC protocols that can withstand quantum attacks. We first present the design and analysis of an information-theoretic secure oblivious linear evaluation (OLE), namely ${\sf qOLE}$ in the quantum domain, and show that our ${\sf qOLE}$ is safe from external attacks. In addition, our scheme satisfies all the security requirements of a secure OLE. We further utilize ${\sf qOLE}$ as a building block to construct a quantum-safe multiparty private set intersection (MPSI) protocol.
We study the following combinatorial problem. Given a set of $n$ y-monotone \emph{wires}, a \emph{tangle} determines the order of the wires on a number of horizontal \emph{layers} such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset~$L$ of \emph{swaps} (that is, unordered pairs of wires) and an initial order of the wires, a tangle \emph{realizes}~$L$ if each pair of wires changes its order exactly as many times as specified by~$L$. \textsc{List-Feasibility} is the problem of finding a tangle that realizes a given list~$L$ if such a tangle exists. \textsc{Tangle-Height Minimization} is the problem of finding a tangle that realizes a given list and additionally uses the minimum number of layers. \textsc{List-Feasibility} (and therefore \textsc{Tangle-Height Minimization}) is NP-hard [Yamanaka, Horiyama, Uno, Wasa; CCCG 2018]. We prove that \textsc{List-Feasibility} remains NP-hard if every pair of wires swaps only a constant number of times. On the positive side, we present an algorithm for \textsc{Tangle-Height Minimization} that computes an optimal tangle for $n$ wires and a given list~$L$ of swaps in $O((2|L|/n^2+1)^{n^2/2} \cdot \varphi^n \cdot n)$ time, where $\varphi \approx 1.618$ is the golden ratio and $|L|$ is the total number of swaps in~$L$. From this algorithm, we derive a simpler and faster version to solve \textsc{List-Feasibility}. We also use the algorithm to show that \textsc{List-Feasibility} is in NP and fixed-parameter tractable with respect to the number of wires. For \emph{simple} lists, where every swap occurs at most once, we show how to solve \textsc{Tangle-Height Minimization} in $O(n!\varphi^n)$ time.
In multi-turn dialog, utterances do not always take the full form of sentences \cite{Carbonell1983DiscoursePA}, which naturally makes understanding the dialog context more difficult. However, it is essential to fully grasp the dialog context to generate a reasonable response. Hence, in this paper, we propose to improve the response generation performance by examining the model's ability to answer a reading comprehension question, where the question is focused on the omitted information in the dialog. Enlightened by the multi-task learning scheme, we propose a joint framework that unifies these two tasks, sharing the same encoder to extract the common and task-invariant features with different decoders to learn task-specific features. To better fusing information from the question and the dialog history in the encoding part, we propose to augment the Transformer architecture with a memory updater, which is designed to selectively store and update the history dialog information so as to support downstream tasks. For the experiment, we employ human annotators to write and examine a large-scale dialog reading comprehension dataset. Extensive experiments are conducted on this dataset, and the results show that the proposed model brings substantial improvements over several strong baselines on both tasks. In this way, we demonstrate that reasoning can indeed help better response generation and vice versa. We release our large-scale dataset for further research.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191