Given a composite null $ \mathcal P$ and composite alternative $ \mathcal Q$, when and how can we construct a p-value whose distribution is exactly uniform under the null, and stochastically smaller than uniform under the alternative? Similarly, when and how can we construct an e-value whose expectation exactly equals one under the null, but its expected logarithm under the alternative is positive? We answer these basic questions, and other related ones, when $ \mathcal P$ and $ \mathcal Q$ are convex polytopes (in the space of probability measures). We prove that such constructions are possible if and only if $ \mathcal Q$ does not intersect the span of $ \mathcal P$. If the p-value is allowed to be stochastically larger than uniform under $P\in \mathcal P$, and the e-value can have expectation at most one under $P\in \mathcal P$, then it is achievable whenever $ \mathcal P$ and $ \mathcal Q$ are disjoint. More generally, even when $ \mathcal P$ and $ \mathcal Q$ are not polytopes, we characterize the existence of a bounded nontrivial e-variable whose expectation exactly equals one under any $P \in \mathcal P$. The proofs utilize recently developed techniques in simultaneous optimal transport. A key role is played by coarsening the filtration: sometimes, no such p-value or e-value exists in the richest data filtration, but it does exist in some reduced filtration, and our work provides the first general characterization of this phenomenon. We also provide an iterative construction that explicitly constructs such processes, and under certain conditions it finds the one that grows fastest under a specific alternative $Q$. We discuss implications for the construction of composite nonnegative (super)martingales, and end with some conjectures and open problems.
相關內容
The article concerns low-rank approximation of matrices generated by sampling a smooth function of two $m$-dimensional variables. We refute an argument made in the literature that, for a specific class of analytic functions, such matrices admit accurate entrywise approximation of rank that is independent of $m$. We provide a theoretical explanation of the numerical results presented in support of this argument, describing three narrower classes of functions for which $n \times n$ function-generated matrices can be approximated within an entrywise error of order $\varepsilon$ with rank $\mathcal{O}(\log(n) \varepsilon^{-2} \mathrm{polylog}(\varepsilon^{-1}))$ that is independent of the dimension $m$: (i) functions of the inner product of the two variables, (ii) functions of the squared Euclidean distance between the variables, and (iii) shift-invariant positive-definite kernels. We extend our argument to low-rank tensor-train approximation of tensors generated with functions of the multi-linear product of their $m$-dimensional variables. We discuss our results in the context of low-rank approximation of attention in transformer neural networks.
Determining the complexity of computing Gr\"{o}bner bases is an important problem both in theory and in practice, and for that the solving degree plays a key role. In this paper, we study the solving degrees of affine semi-regular sequences and their homogenized sequences. Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gr\"{o}bner bases of the ideal generated by an affine semi-regular sequence. This paper is a sequel of the authors' previous work and gives additional results on the solving degrees and important behaviors of Gr\"obner basis computation. We also define the generalized degree of regularity for a sequence of homogeneous polynomials. For the homogenization of an affine semi-regular sequence, we relate its generalized degree of regularity with its maximal Gr\"{o}bner basis degree (i.e., the solving degree of the homogenized sequence). The definition of a generalized (cryptographic) semi-regular sequence is also given, and it derives a new cryptographic assumption to estimate the security of cryptosystems and signature schemes. From our experimental observation, we raise a conjecture and some questions related to this generalized semi-regularity. These new definitions and our results provide a theoretical formulation of (somehow heuristic) discussions done so far in the cryptographic community.
Efficiently enumerating all the extreme points of a polytope identified by a system of linear inequalities is a well-known challenge issue.We consider a special case and present an algorithm that enumerates all the extreme points of a bisubmodular polyhedron in $\mathcal{O}(n^4|V|)$ time and $\mathcal{O}(n^2)$ space complexity, where $ n$ is the dimension of underlying space and $V$ is the set of outputs. We use the reverse search and signed poset linked to extreme points to avoid the redundant search. Our algorithm is a generalization of enumerating all the extreme points of a base polyhedron which comprises some combinatorial enumeration problems.
We consider the problem of enumerating all minimal transversals (also called minimal hitting sets) of a hypergraph $\mathcal{H}$. An equivalent formulation of this problem known as the \emph{transversal hypergraph} problem (or \emph{hypergraph dualization} problem) is to decide, given two hypergraphs, whether one corresponds to the set of minimal transversals of the other. The existence of a polynomial time algorithm to solve this problem is a long standing open question. In \cite{fredman_complexity_1996}, the authors present the first sub-exponential algorithm to solve the transversal hypergraph problem which runs in quasi-polynomial time, making it unlikely that the problem is (co)NP-complete. In this paper, we show that when one of the two hypergraphs is of bounded VC-dimension, the transversal hypergraph problem can be solved in polynomial time, or equivalently that if $\mathcal{H}$ is a hypergraph of bounded VC-dimension, then there exists an incremental polynomial time algorithm to enumerate its minimal transversals. This result generalizes most of the previously known polynomial cases in the literature since they almost all consider classes of hypergraphs of bounded VC-dimension. As a consequence, the hypergraph transversal problem is solvable in polynomial time for any class of hypergraphs closed under partial subhypergraphs. We also show that the proposed algorithm runs in quasi-polynomial time in general hypergraphs and runs in polynomial time if the conformality of the hypergraph is bounded, which is one of the few known polynomial cases where the VC-dimension is unbounded.
We establish necessary and sufficient conditions for invertibility of symmetric three-by-three block matrices having a double saddle-point structure \fb{that guarantee the unique solvability of double saddle-point systems}. We consider various scenarios, including the case where all diagonal blocks are allowed to be rank deficient. Under certain conditions related to the nullity of the blocks and intersections of their kernels, an explicit formula for the inverse is derived.
We prove that the Weihrauch degree of the problem of finding a bad sequence in a non-well quasi order ($\mathsf{BS}$) is strictly above that of finding a descending sequence in an ill-founded linear order ($\mathsf{DS}$). This corrects our mistaken claim in arXiv:2010.03840, which stated that they are Weihrauch equivalent. We prove that K\"onig's lemma $\mathsf{KL}$ and the problem $\mathsf{wList}_{2^{\mathbb{N}},\leq\omega}$ of enumerating a given non-empty countable closed subset of $2^\mathbb{N}$ are not Weihrauch reducible to $\mathsf{DS}$ either, resolving two main open questions raised in arXiv:2010.03840.
A separating system of a graph $G$ is a family $\mathcal{S}$ of subgraphs of $G$ for which the following holds: for all distinct edges $e$ and $f$ of $G$, there exists an element in $\mathcal{S}$ that contains $e$ but not $f$. Recently, it has been shown that every graph of order $n$ admits a separating system consisting of $19n$ paths [Bonamy, Botler, Dross, Naia, Skokan, Separating the Edges of a Graph by a Linear Number of Paths, Adv. Comb., October 2023], improving the previous almost linear bound of $\mathrm{O}(n\log^\star n)$ [S. Letzter, Separating paths systems of almost linear size, Trans. Amer. Math. Soc., to appear], and settling conjectures posed by Balogh, Csaba, Martin, and Pluh\'ar and by Falgas-Ravry, Kittipassorn, Kor\'andi, Letzter, and Narayanan. We investigate a natural generalization of these results to subdivisions of cliques, showing that every graph admits both a separating system consisting of $41n$ edges and cycles, and a separating system consisting of $82 n$ edges and subdivisions of $K_4$.
We show that the limiting variance of a sequence of estimators for a structured covariance matrix has a general form that appears as the variance of a scaled projection of a random matrix that is of radial type and a similar result is obtained for the corresponding sequence of estimators for the vector of variance components. These results are illustrated by the limiting behavior of estimators for a linear covariance structure in a variety of multivariate statistical models. We also derive a characterization for the influence function of corresponding functionals. Furthermore, we derive the limiting distribution and influence function of scale invariant mappings of such estimators and their corresponding functionals. As a consequence, the asymptotic relative efficiency of different estimators for the shape component of a structured covariance matrix can be compared by means of a single scalar and the gross error sensitivity of the corresponding influence functions can be compared by means of a single index. Similar results are obtained for estimators of the normalized vector of variance components. We apply our results to investigate how the efficiency, gross error sensitivity, and breakdown point of S-estimators for the normalized variance components are affected simultaneously by varying their cutoff value.
Bent functions are maximally nonlinear Boolean functions with an even number of variables, which include a subclass of functions, the so-called hyper-bent functions whose properties are stronger than bent functions and a complete classification of hyper-bent functions is elusive and inavailable.~In this paper,~we solve an open problem of Mesnager that describes hyper-bentness of hyper-bent functions with multiple trace terms via Dillon-like exponents with coefficients in the extension field~$\mathbb{F}_{2^{2m}}$~of this field~$\mathbb{F}_{2^{m}}$. By applying M\"{o}bius transformation and the theorems of hyperelliptic curves, hyper-bentness of these functions are successfully characterized in this field~$\mathbb{F}_{2^{2m}}$ with~$m$~odd integer.
The infinite pigeonhole principle for $k$ colors ($\mathsf{RT}_k$) states, for every $k$-partition $A_0 \sqcup \dots \sqcup A_{k-1} = \mathbb{N}$, the existence of an infinite subset~$H \subseteq A_i$ for some~$i < k$. This seemingly trivial combinatorial principle constitutes the basis of Ramsey's theory, and plays a very important role in computability and proof theory. In this article, we study the infinite pigeonhole principle at various levels of the arithmetical hierarchy from both a computability-theoretic and reverse mathematical viewpoint. We prove that this hierarchy is strict over~$\mathsf{RCA}_0$ using an elaborate iterated jump control construction, and study its first-order consequences. This is part of a large meta-mathematical program studying the computational content of combinatorial theorems.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191