跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+0已有论文修订
+91新增 AI 导读

arXiv 最近完成扫描:2026-11-22 21:02 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

统计 2026-11-21 23:35 — 2026-11-22 23:35(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-22 21:02最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 380 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-22 21:00(北京时间)
新论文 · v1arXiv:2611.15074

Tokenization: Hardness and Bicriteria Approximation Algorithms

Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran

原文摘要

We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(γ,γ)$-bicriteria algorithm, with $γ= \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $γK$ with number of tokens at most $γ{\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.

cs.DS · cs.AI · cs.CC

版本更新 · v2arXiv:2611.06658

The determinantal complexity of the 4*4 permanent is 15

Karthik Sheshadri

原文摘要

The best known lower bound on the determinantal complexity of the 4x4 permanent is 10. In this short note, I prove that this value is exactly 15: the 4x4 permanent is the determinant of a 15x15 matrix of affine linear forms, and cannot be that of any smaller matrix. To do so, I must establish both a lower and upper bound. To establish the upper bound, I use Grenet's construction of size 2^n-1. Hence that construction is optimal at n=4 (and n=3). This now constitutes the first knwon exact value of the determinantal complexity of the permanent at n=4. Only the value at n=3 was exactly known, prior to this note. The general quadratic bound only gives 8 for n=4. To establish the lower bound, I work from a normal form at a zero of the permanent. In the first row (and column) of the normal form, the linear forms vanish on a linear space inside the singular locus of the permanent. A hessian inequality bounds the size of the matrix in terms of that space. Then, a matrix of sie 14 foces the space into any of nine corordinate types. The forcing is either up to symmetry, or else into a family that degenerates to one of them. I then rule out every case. All involved computations are exact. In respect of the claim, I have made all certificates public.

cs.CC

版本更新 · v15arXiv:2203.05022

A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)

Gao Ming

原文摘要

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, whose encryption and decryption can be completed in linear time. The key consists of 12 variables, for the attacker, in the case when only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations about 12 unknown variables $(w_{1}, w_{2}, ..., w_{11}, w_{12})$ together with some implicit variables which are generated by the encryption process. In this paper, we will prove that there is no universal algorithm without brute-force searching at least one variable during the process of verifying five variables $(w_{1}$, $w_{2}$, $w_{3}$, $w_{4}$, $w_{9})$ whose computational complexity is not greater than solving the 12 variables......

cs.CC · cs.IT

新论文 · v1arXiv:2611.14892

Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means

Karthik C. S., Dor Minzer

原文摘要

In the Euclidean $k$-means problem, we are given a set of $n$ points in $\mathbb{R}^d$, and the goal is to find $k$ representative points in space so as to minimize the sum of the squared distances from each point to its closest representative. Algorithmically, de la Vega, Karpinski, Kenyon, and Rabani [STOC'03] and Kumar, Sabharwal, and Sen [JACM'10] obtain a $(1+\varepsilon)$-approximation for high-dimensional Euclidean $k$-means in time $2^{(k/\varepsilon)^{O(1)}} \cdot dn^{O(1)}$, which was subsequently improved to $2^{\tilde{O}(k/\varepsilon)} + O(ndk)$ by Feldman, Monemizadeh, and Sohler [SoCG'07]. On the lower-bound side, a recent work of Cohen-Addad, Karthik, Saulpic, and Schwiegelshohn [SoCG'26] proposed the Exponential Time for Expanders Hypothesis (XXH), which asserts exponential-time hardness for $(1+\varepsilon)$-approximating Vertex Cover on vertex expanders, and used it to prove nearly matching running time lower bound whenever $k=\tildeω(1/\varepsilon)$. We observe that XXH does not hold in the parameter regime needed for the above result, and show how to repair their reduction under a more standard assumption. More precisely, we show that assuming the Almost Exponential Time Hypothesis for 3-SAT (Almost ETH), for every constant $β\in(0,1)$, Euclidean $k$-means in $\mathbb{R}^d$ has no $(1+\varepsilon)$-approximation algorithm running in time $2^{(k/\varepsilon)^{1-β}}\text{poly}(n,d)$, whenever $k=\tildeω(1/\varepsilon)$. By modifying the construction, we also obtain a similar result for approximating the Euclidean $k$-median problem.

cs.CG · cs.CC · cs.DS · stat.ML

版本更新 · v2arXiv:2610.30907

Near-Quadratic Time Multivariate Polynomial Interpolation

Chandra Kanta Mohapatra

原文摘要

Let $\F$ be a finite field. Given $N$ distinct points $\bmα_1,\ldots,\bmα_N \in \F^m$ and associated values $β_1,\ldots,β_N \in \F$, we study the problem of computing an $m$-variate polynomial $f(\vy) \in \F[\vy]$ of individual degree less than $d$, with $d^m \ge N$, that satisfies $f(\bmα_i)=β_i$ for all $i\in[N]$, whenever such an $f$ exists. This is known as the\textit{ multivariate polynomial interpolation} problem. In this work, given $N=d^m$, we present a deterministic algorithm for multivariate polynomial interpolation over an arbitrary finite field $\F$ that runs in near-quadratic time $N^{2+o(1)}\poly(m,d,\log|\F|)$, assuming $d$ is $ω(1)$. This bound holds whenever the associated \emph{multivariate Vandermonde} matrix is nonsingular, has constant co-rank, or admits some special structure. In the general case, we give a randomized Las Vegas algorithm attaining the same near-quadratic running time, provided the finite field is sufficiently large and $d$ grows similar to the previous case. Unlike other multivariate interpolation strategies, we do not assume black-box access to the polynomial. In particular, we are not permitted to query arbitrary input points to obtain their evaluations. Our interpolation result follows by combining Wiedemann's classical approach~\cite{w86} for solving sparse linear systems with known bounds for fast \emph{multivariate multipoint evaluation} over finite fields~\cite{umans08, KU11, BGKM23, BGGKU24}. Specifically, our deterministic interpolation strategy relies on a deterministic variant of Wiedemann's approach, which is more commonly used in the randomized setting.

cs.DS · cs.CC · cs.SC

新论文 · v1arXiv:2611.14837

Two-Stage Mixed-Integer Quadratic Programming in Polynomial Time

Alberto Del Pia

原文摘要

Lenstra showed that mixed-integer linear programming can be solved in polynomial time when the number of integer variables is fixed and the number of continuous variables is arbitrary. Mixed-integer quadratic programming (MIQP) can be solved in polynomial time when the total number of variables is fixed. However, since MIQP is NP-hard already without integer variables, the analog of Lenstra's result fails unless P = NP. Hence, polynomial-time algorithms for MIQP with an arbitrary number of continuous variables must exploit additional structure. We study MIQPs with two-stage structure, which underlies Benders decomposition and two-stage stochastic programming. A few linking variables, including all integer variables, are coupled with many blocks of continuous variables that interact only through them, both in the constraints and in the objective. We give a polynomial-time algorithm for MIQP with an arbitrary quadratic objective when the number of linking variables and the block size are fixed, while the number of blocks, and hence the number of variables, is arbitrary. The case with no blocks is MIQP in fixed dimension. None of our assumptions can be dropped. Unless P = NP, the number of linking variables and the block size must both be fixed, the blocks cannot interact or contain integer variables, and large blocks cannot be allowed even if their objective is linear. Unless FPT = W[1], the exponent of the running time must depend on both the number of linking variables and the block size.

math.OC · cs.CC · cs.DS

新论文 · v1arXiv:2611.14454

带反射神谕的Solomonoff归纳

Solomonoff Induction with Reflective Oracles

Damini Kusum

AI 速读 基于摘要

研究基于反射神谕的Solomonoff归纳变体的预测性质,作者报告该最优预测器能对抗仅指定部分数据生成过程的可计算预测策略。

cs.CC

查看原文摘要

We study predictive properties of a reflective variant of Solomonoff induction formulated using reflective oracles (Fallenstein et al. 2015, Wyeth et al. 2025). We show that the resulting optimal predictor succeeds against computable predictive strategies that specify only part of the data-generating process. The argument relies on the fact that hypotheses computable from the predictor's own conditional probabilities remain within the reflective hypothesis class. In particular, the predictor learns incomplete models specified by computable interval restrictions on next-bit probabilities. We also establish weighted forms of unbiasedness and calibration. Finally, we discuss whether an optimal predictor's conditional probabilities suffice to compute every hypothesis in the reflective class.

新论文 · v1arXiv:2611.14411

算术化 k-正交向量问题的均匀量子平均情形细粒度困难性

Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized $k$-Orthogonal Vectors

Dhruv Prasad Deshpande, Abhishek Mishra

AI 速读 基于摘要

在量子强指数时间假设(QSETH)下,作者给出算术化 k-正交向量多项式在两类规范素数域上、包含全部初始化开销的均匀量子平均情形细粒度困难性归约。

cs.CC

查看原文摘要

We study exact evaluation of the arithmetized $k$-Orthogonal Vectors polynomial $FOV^k$ of Ball et al. (2017, 2018). For every fixed integer $k \geq 3$, set $d(n) = \left \lceil \log^2 n \right \rceil$. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant $\varepsilon > 0$, no uniform quantum algorithm runs in $O(n^{k/2 - \varepsilon})$ time on every input and evaluates this polynomial correctly with probability at least $3 / 4$ over a uniformly random input in $\mathbb F_{p(n)}^{knd(n)}$ and the algorithm's internal randomness, for all sufficiently large $n$. This holds when $p(n)$ is the smallest prime greater than $n^{k - 1}$ and when it is the smallest prime greater than $n^k$. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo $p(n)$; otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.

新论文 · v1arXiv:2611.14379

判定有限关系结构的Maltsev多态性存在性的复杂性

Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures

Dejan Delic, Ali Syed

AI 速读 基于摘要

作者报告判定有限关系结构是否具有Maltsev多态性可在多项式时间内完成,并借助二元关系矩形性给出归约证明。

cs.CC

查看原文摘要

In this article, we show that the problem of deciding whether a finite relational structure $\mathbf{A}$ admits a Maltsev polymorphism is a computational problem, which can be solved in polynomial time. We provide a proof of this result by reducing the problem to deciding whether a binary relational structure, associated with $\mathbf{A}$ admits such a polymorphism. In our construction of such an algorithm, we make an extensive use of a property of binary relations, which is implied by the existence of a Maltsev polymorphism, the so-called rectangularity property.

版本更新 · v2arXiv:2609.01469

某些秩2分圆模上的SVP是NP难的

SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules

Jiaqi Liu, Yansong Feng, Yanbin Pan

AI 速读 基于摘要

作者证明:在分圆整数环的秩2全秩自由子模上,ℓ2范数下最短向量问题的判定版本是NP完全的,并给出从X3C出发的确定性多项式时间归约。

cs.CC · cs.CR

查看原文摘要

Let $q$ be an odd prime. Let $ζ_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(ζ_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[ζ_q]$. As $q$ ranges over odd primes, we prove that the decision version of the Shortest Vector Problem ($\mathsf{SVP}$) in the canonical $\ell_2$-norm is $\mathsf{NP}$-complete on full-rank free submodules of $\mathcal{O}_K^2$ by giving a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. The main obstacle is closure under the action of $\mathcal{O}_K$. A module containing a nonzero vector also contains every scalar multiple of that vector by a nonzero element of $\mathcal{O}_K$, and some of these multiples may be shorter. Three ideas overcome this obstacle. First, we map the Bennett--Peikert Reed--Solomon lattice to a principal cyclotomic ideal and use Wan's point-count estimates to prove that a coset of this ideal contains many binary coefficient representatives. Second, we construct a checker whose canonical squared norm encodes the X3C equations, with a controlled nonnegative error term. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out short vectors in NO instances. Each constructed instance consists of an odd prime $q$, two integral generators whose $2\times2$ generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives $\mathsf{NP}$-hardness of search-$\mathsf{SVP}$ under deterministic polynomial-time Turing reductions with at most one oracle call.

新论文 · v1arXiv:2611.14334

$\mathsf{SVP}_\infty$ 在二的幂次分圆理想中是 NP-难的

$\mathsf{SVP}_\infty$ Is NP-Hard for Power-of-two Cyclotomic Ideals

Yansong Feng, Jiaqi Liu, Hengyi Luo, Yanbin Pan

AI 速读 基于摘要

作者报告证明了在二的幂次分圆环的主理想与秩二自由模上,系数 $\ell_\infty$ 范数下的精确判定 SVP 是 NP-完全的,并给出从子集和问题的确定性多项式时间多一归约。

cs.CC

查看原文摘要

We prove that exact decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm is $\mathsf{NP}$-complete for principal ideals and free modules of rank two over the cyclotomic rings $R_n=\mathbb{Z}[X]/(X^n+1)$, where $n$ ranges over powers of two. For each case, we give a deterministic polynomial-time many-one reduction from the Subset Sum problem. For an instance with $s$ positive input integers, the output lattice has dimension $O(s)$. A solution to the original Subset Sum instance can be recovered in polynomial time from any nonzero output lattice vector of norm at most the specified bound. We also transfer these reductions from $R_n$ to the power-of-two cyclic rings $S_{2n}=\mathbb{Z}[X]/(X^{2n}-1)$. This gives $\mathsf{NP}$-completeness of decision-$\mathsf{SVP}$ in the coefficient $\ell_\infty$-norm for principal ideals and free modules of any fixed positive rank over these rings.

新论文 · v1arXiv:2611.14282

从最坏情况到平滑复杂度:连续优化中的平滑分析框架

From Worst-Case to Smoothed Complexity in Continuous Optimization

Daniel Cortild, Coralia Cartis

AI 速读 基于摘要

作者提出一个平滑分析框架,研究经典连续优化算法在任意函数随机扰动下的表现,并给出若干标准方法的平滑复杂度保证。

math.OC · cs.CC

查看原文摘要

Worst-case complexity bounds often fail to reflect the practical performance of optimization algorithms, while average-case complexity heavily relies on the distribution of the input. In this work, we develop a smoothed-analysis framework for classical continuous optimization algorithms by studying their behaviour on random perturbations of arbitrary functions. Our main contribution is to apply methods suited for non-degenerate functions to perturbations of degenerate functions, thereby recovering the faster best-known rates for the non-degenerate class. We derive smoothed complexity guarantees for several standard methods, including (Accelerated) Gradient Descent, Conjugate Gradient, and Newton-type methods, under various settings including nonconvex ones, and show that these bounds can substantially improve upon their worst-case guarantees, bringing them closer to the practical behaviour of the respective methods.

新论文 · v1arXiv:2611.14191

The Monophonic Directed Convexities

Júlio Araújo, Ana Karolinna Maia, Thiago Marcilon, Nicolas Nisse, Rudini M. Sampaio

原文摘要

Graph Convexity is a topic with many papers in the literature, especially on the $P_3$, geodesic, and monophonic convexities in undirected graphs. Regarding directed graphs, Erd{\H o}s et al. in 1972 and Chartrand and Zhang in 2000 obtained the first results on the $P_3$ and geodesic convexities for directed graphs, respectively. In this paper, we start the investigation of monophonic convexity on directed graphs. We define two convexities, the monophonic and the strong monophonic directed convexities, related to the minimal and the induced directed paths, respectively. We show that deciding whether a set is convex is polynomial-time solvable in the monophonic convexity, but coNP-complete in the strong monophonic convexity. For both convexities, we prove that the hull number is NP-complete even in DAGs. Regarding the monophonic convexity, we prove that the hull number is polynomial time solvable in tournaments, but the interval number is NP-complete in tournaments and also in bipartite oriented graphs.

cs.CC · math.CO

版本更新 · v9arXiv:2503.20550

Structural Origins of Cubic Complexity in Pebble Motion

Tomoki Nakamigawa, Tadashi Sakuma

原文摘要

The pebble motion problem (PMP) asks whether one configuration of labeled pebbles on a graph can be transformed into another by moving pebbles to adjacent unoccupied vertices. Kornhauser, Miller, and Spirakis proved that the worst-case shortest solution length on an $N$-vertex graph is $Θ(N^3)$, but the graph structures responsible for this cubic behavior remained unclear. We first show that cubic complexity cannot occur on trees: every feasible instance on an $N$-vertex tree admits a solution sequence of length $\mathrm{O}(N^2\log N)$, constructible in time linear in its length. This is the first $\mathrm{o}(N^3)$ upper bound for PMP on trees. We then extend the method to general graphs. When $2\le N-n=\mathrm{O}(1)$, every instance on a feasible puzzle admits a solution of length $\mathrm{O}(n\,\mathrm{CL}(G)\,\mathrm{D}(G))$, where $\mathrm{D}(G)$ is the diameter and $\mathrm{CL}(G)$ is the maximum length of a shortest cycle through a vertex; this recovers the classical $\mathrm{O}(N^{3/2})$ bound for square grids. We further show that any graph with worst-case shortest solution length $Θ(N^3)$ has a unique biconnected component $X$ of order $Θ(N)$, while all structures attached through any one cut vertex of $X$ have bounded total size. Moreover, $X$ contains no cycle of unbounded sublinear order, and any two intersecting cycles of order $Θ(N)$ share at least as many vertices as there are blanks. Finally, cubic complexity occurs when a cycle of order $Θ(N)$ contains all but $\mathrm{O}(1)$ vertices, whereas two $Θ(N)$-cycles meeting at one vertex have complexity exactly $Θ(N^2\log N)$. We conjecture that the former construction essentially characterizes the cubic regime.

math.CO · cs.CC · cs.DM

版本更新 · v4arXiv:2509.13423

Computational complexity of Berry phase estimation in topological phases of matter

Ryu Hayakawa, Kazuki Sakamoto, Chusei Kiumi

原文摘要

The Berry phase is a fundamental quantity in the classification of topological phases of matter. In this paper, we present a new quantum algorithm and several complexity-theoretical results for the Berry phase estimation (BPE) problems. Our new quantum algorithm achieves BPE in a more general setting than previously known quantum algorithms, with a theoretical guarantee. For the complexity-theoretic results, we consider two main cases. First, we prove $\mathsf{BQP}$-completeness when we are given a guiding state that has a large overlap with the ground state. This result establishes an exponential quantum speedup for estimating the Berry phase. Second, we prove $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$-completeness when we have an $\textit{a priori}$ bound for the ground-state energy. Here, $\mathsf{UQMA}$ is the unique witness version of $\mathsf{QMA}$, and $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$ precisely captures the complexity of BPE without the known guiding state. Remarkably, this problem is, to our knowledge, the first natural problem complete for $\mathsf{UQMA} \cap \mathsf{co}$-$\mathsf{UQMA}$. These results advance the role of quantum computing in the study of topological phases of matter and provide a pathway for clarifying the connection between topological phases of matter and computational complexity.

quant-ph · cond-mat.str-el · cs.CC

版本更新 · v3arXiv:2601.04072

The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three

Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard

原文摘要

Lecomte and Ramakrishnan (arXiv'26) recently presented a depth-three circuit of size $2^{O(\sqrt{n})}$ that computes the Majority function, refuting a long held conjecture. Nevertheless, as a fundamental computational primitive which ubiquitously appears across computer science, determining the exact complexity of Majority down to the constant in the exponent, remains important. Gurumukhani et al. (CCC'24) initiated the study of optimal $Σ^k_3$ circuits computing the Majority function. In this work, we determine the exact $Σ^3_3$ complexity of Majority up to polynomial factors. We show that for any $t \le n/2$, given an $n$-variate $t$-threshold 3-CNF, i.e., with no satisfying assignment with Hamming weight less than $t$, the number of weight-$t$ satisfying assignments is at most $2^t(3/2)^{(n-t)/2}$. Along with a matching construction for $t = n/2$, the result implies that the size of the smallest $Σ^3_3$ circuit computing Majority is exactly $poly(n)(2/6^{1/4})^n$. The proof involves two main ingredients: - Reduction to monotone: We formulate a linear program (LP) which is defined only with respect to the monotone part of the formula. We show that bounding the cost function of this LP implies our desired upper bound on the number of minimum weight solutions of the general formula. - Structure of extremal formulas: To bound the cost function of the LP, we develop an extensive inductive argument. The inductive steps are determined by a close inspection of the local structure of extremal formulas with respect to minimum weight. Our result has a natural hypergraph interpretation: it bounds the number of independent sets of size $n-t$ under the condition that the independence number is $n-t$. This is a generalized hypergraph Turán problem and coincides with the classical hypergraph Turán problem at threshold $t=n-k$ for $k$-uniform hypergraphs.

cs.CC

新论文 · v1arXiv:2611.13917

Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path

Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider, Torsten Ueckerdt

原文摘要

We examine the computational complexity of well-known problems on subgraphs of the strong product of two paths. Namely, for Max Cut we show NP-hardness on induced subgraphs of $P \boxtimes P$ answering a question by Dvořák, Huynh, Joret, Liu, and Wood (2021). For 3-Edge Coloring we show NP-hardness on subgraphs of $P \boxtimes P$ and that it is equivalent to 3-Edge Coloring on planar graphs for induced subgraphs of $P \boxtimes P$. It is a long standing open question whether 3-Edge Coloring on planar graphs is NP-hard. As a second contribution, we consider graphs of the form $G \boxtimes P$ and show that Feedback Vertex Set on these graphs is FPT in the clique-width of $G$. Furthermore, we show that it can be solved in polynomial time if $G$ is chordal or co-comparable and that the computational complexity depends on the parity of $P$ if $G$ is bipartite. Namely, it is solvable in polynomial time if $P$ has an even number of vertices but is NP-complete otherwise. For Max Cut, we show that it can be solved in polynomial time if $G$ is bipartite.

cs.CC · cs.DM · math.CO

新论文 · v1arXiv:2611.13787

Local Modifications of Nearest-Neighbor and Min-Plus Representations

Liliia Redina

原文摘要

We study how changing a Boolean-valued function at $d$ inputs affects the size and precision of its exact representations. Starting from a representation of size $m$, we prove four bounds, two for nearest-neighbor (NN) representations and two for integer min-plus representations. (i) For NN representations on a finite subset of $\mathbb{R}^n$ with $n\ge2$, at most $m+2d$ anchors suffice. The coefficient $2$ is optimal: on a three-point domain, changing one value can increase the minimum number of anchors from one to three. (ii) For NN representations on the Boolean cube with rational anchors, let $R$ be the maximum original coordinate bit length, and let $Δ$ be the maximum bit length of the least common denominator of any one original anchor's coordinates. We construct a representation with at most $m+3d$ anchors on a common dyadic grid and coordinate bit length $O(R+Δ+\log(n+1))$. (iii) For integer min-plus representations on the Boolean cube, we give a construction that keeps the original $m$ forms and their labels and adds at most $d$ new forms. Its maximum weight is at most $W+2n$, where $W$ is the largest absolute original coefficient, including constant terms. (iv) For integer min-plus representations on a finite rational domain $X\subset\mathbb{Q}^n$, at most $m+2d$ forms suffice. Their maximum weight is polynomially bounded in $m,d,W,n,|X|$, the coordinate bound, and the common denominator of $X$. The coefficient $2$ is again optimal: on a three-point domain, changing one value can increase the minimum number of forms from one to three. These bounds imply stability under polynomially many changes on the cube for polynomial-size representations, including those with polynomially bounded NN coordinate bit length or min-plus weight.

cs.CC · cs.DM

新论文 · v1arXiv:2611.13600

Parameterized Complexity and Geometric Approximation of Riesz Energy Subset Selection

Michael Emmerich, Soumen Atta

原文摘要

We choose $k$ of $n$ sites to minimize Riesz $s$-energy, in which a pair at distance $t$ contributes $t^{-s}$. For $s=2$, exact selection is polynomial on a line but NP-hard in the plane. Adapting the proxy lemma of Ceccarello et al. gives an efficient parameterized approximation scheme (EPAS) for fixed Euclidean dimension and fixed $s>0$. To sharpen the bound, we start with a geometric packing. Farthest-first traversal gives $2k$ centers separated by at least the last insertion distance $r$. If one site of an optimum is removed, each of the $k-1$ remaining sites excludes at most one center closer than $r/2$, leaving at least $k+1$ centers free. The new step is a discrete exchange bound: the removed site's interaction energy is at most the average it would contribute at those free centers. In the plane at $s=2$, this reduces the representative bound from $O(k^2\log(2k)/\varepsilon^2)$ for a packing estimate of total energy to $O(k\log(2k)/\varepsilon^2)$, independently of $n$. Rational planar examples show that the resulting separation scale $r/\sqrt{\log(2k)}$ is sharp. A $(1+\varepsilon)$ approximation on rational planar sites takes $O(nk+n\log n)+(C\log(2k)/\varepsilon^2)^k$ operations of polynomial bit cost. The observed number $M$ of representatives determines the search size $\binom{M}{k}$. With one million sites, $k=5$ and $\varepsilon=1/2$, the exchange grid left 252 subsets on clustered inputs and about $9.3\times10^{26}$ on uniform inputs. The method extends to metrics of bounded doubling dimension and to compact domains with effective geometric routines, including filled simple polygons. At $s=2$, exact decision on metrics with nonzero distances in $\{1,2\}$ is W[1]-complete in $k$. A gap that shrinks with $k$ rules out a deterministic EPAS on unrestricted metrics unless FPT = W[1].

cs.CG · cs.CC · cs.DS

新论文 · v1arXiv:2611.13568

Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets

Kundan Baliga, Aiden Xie, Aditya Byju

原文摘要

Tokenisers such as Byte-Pair Encoding (BPE) shorten text by repeatedly merging an adjacent pair of symbols into a new one; fewer tokens mean less computation. We ask whether an efficient algorithm can choose $k$ merges that leave a string of length $n$ almost as short as possible; doing nothing is already within a factor $n$. We prove that, unless P = NP, no polynomial-time algorithm comes within a factor $c\,n/\log n$, for some constant $c>0$, already for one binary string and for BPE-style merges that replace every occurrence. The key idea is that $k$ merges form a grammar with $k$ rules: a vertex-cover gap becomes a grammar-size gap, which we amplify with relabelled copies, encode in binary and realise with explicit merges. For merges that may skip occurrences, a simple algorithm achieves $O(n/\log\log n)$, and no Karp reduction can prove hardness beyond order $n/\log n$ unless coNP $\subseteq$ NP/poly. Over a one-letter alphabet, both tokenisation problems left open by Kastreva et al. are strongly NP-complete on datasets with repeated strings.

cs.DS · cs.CC · cs.CL

版本更新 · v2arXiv:2609.37431

Query Complexity of Testing Structured Parenthesis Languages

Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova

原文摘要

We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word and must distinguish valid inputs from words that are far in Hamming distance, while inspecting only a sublinear number of positions. Our results sharpen the boundary between constant-query testability and polynomial query complexity. First, we prove an $Ω(n^{2/5})$ lower bound for testing Dyck languages $D_m$ with any fixed number $m\ge2$ of parenthesis types, improving the previous $Ω(n^{1/5})$ lower bound of Fischer, Magniez, and Starikovskaya (SODA `18) and nearly matching their upper bound of $O(n^{2/5+o(1)})$. Furthermore, we show that all nonadaptive algorithms for these problems require $Ω(n^{1/2})$ queries. Our lower bounds use a Pólya-urn process to construct the hard distribution; Second, we identify a broad class of weighted-parenthesis languages, which we call {\em excursion languages,} that remain constant-query testable. These languages encode bounded-step walks that stay nonnegative and return to zero. For every fixed excursion language, we give a nonadaptive tester with query complexity $O(1/\varepsilon^2)$, and we prove this dependence on $\varepsilon$ is optimal, even for adaptive algorithms. As a special case, we obtain the tight $Θ(1/\varepsilon^2)$ query complexity of testing $D_1$, improving the previous $O(\log(1/\varepsilon)/\varepsilon^2)$ upper bound and giving the first matching two-sided-error lower bound. Third, we construct a simple hard language, Hidden String, that is generated by a deterministic linear grammar but nevertheless requires $Ω(n^{2/5})$ adaptive queries and $Ω(n^{1/2})$ nonadaptive queries to test. This shows that polynomial query complexity appears even for highly restricted string languages.

cs.DS · cs.CC

版本更新 · v2arXiv:2611.09183

On derandomizing the line-point low-degree test

Prahladh Harsha, Swastik Kopparty, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

原文摘要

We investigate the derandomized version of the classical line-point low-degree test in the high-error regime in the bivariate setting and reveal some unexpected behavior. The classical line-point low-degree test takes an $m$-variate function $f$ over a finite field $\mathbb{F}_q$, queries it along a random line and accepts if the restriction of the function to this line is a low-degree polynomial. The high-error version of (the analysis of) this test asserts that if $f$ has at least $ε$ expected local agreement with a degree-$k$ univariate polynomial on a random line, then in fact $f$ is non-trivially close to some degree-$k$ $m$-variate polynomial even as $ε$ approaches $0$ (provided $q$ is sufficiently large compared to $k$ and $1/ε$). The derandomized version of the problem asks if the same holds when the line is not chosen uniformly over all possible lines but rather from a small set. In this paper we explore the bivariate case ($m=2$). We show, somewhat surprisingly, that there exists a function $f\colon \mathbb{F}_q^2 \to \mathbb{F}_q$ and a set of lines $\mathcal{L}$ in $\mathbb{F}_q^2$ of size nearly $q^{3/2}$ such that on every line in $\mathcal{L}$, $f$ has agreement $\approx 1/2$ on average with some univariate polynomial of degree $k=\sqrt{q}/2$ and yet $f$ is $1 - O(q^{-1/2})$ far from every polynomial of degree $O(k)$. On the positive side, we show that once the field size $q$ is at least $k^2/(ε)^{O(1)}$ such examples disappear and we can get sets of lines of size $O(q/ε^{O(1)})$ on which the low-degree test has a high-error analysis. On the way to our positive result, we show a new high-degree version of the classical two-direction Polishchuk--Spielman divisibility lemma.

cs.CC · cs.IT

新论文 · v1arXiv:2611.13347

Computational Power of Clifford and Ising Quantum Computers

Sawyer Dobson, Zhenghan Wang

原文摘要

We extend the efficient classical simulation of Ising quantum computers from braidings to measurements. We investigate several different definitions of efficient Clifford quantum computation by varying the power of the circuit generator. In case the circuit generator can see the entire input, we give a detailed proof that efficient simulation of classical computation would imply the separation of complexity classes $\mathbf{P}$ and $\mathbf{PSPACE}$. If the circuit generator sees only the input length, we prove that Clifford quantum computers decide what we call affine languages.

quant-ph · cs.CC · math.QA

新论文 · v1arXiv:2611.13281

Constant query LCCs over the reals

Zeev Dvir

原文摘要

This note describes a new construction, found by ChatGPT Astra, of constant query Locally Correctable Codes (LCCs) over the real numbers. Prior constructions of constant query LCCs were exclusive to fields of positive characteristic and were conjectured not to exist over the reals. The construction uses low degree polynomial evaluations over an integer grid, together with a novel sampling procedure which outputs, for a given grid point $P$, a random quadratic curve through $P$ which intersects the grid in many other points (the decoding queries). The sampler is `smooth' in the sense that no grid point is queried with high probability. These codes have the additional property that the queried locations (the curve/grid intersections) are all nearby grid points.

cs.CC · math.CO

版本更新 · v3arXiv:2604.10819

Differentially Private Verification of Distribution Properties

Elbert Du, Cynthia Dwork, Pranay Tankala, Linjun Zhang

原文摘要

A recent line of work initiated by Chiesa and Gur and further developed by Herman and Rothblum investigates the sample and communication complexity of verifying properties of distributions with the assistance of a powerful, knowledgeable, but untrusted prover. In this work, we initiate the study of differentially private distribution property verification. After all, if we do not trust the prover to help us with verification, why should we trust it with our sensitive sample? We map a landscape of differentially private verification of properties of distributions. In the non-private case it is known that one-round private-coin protocols can have substantially lower complexity than public-coin (AM) protocols. In contrast, the possibility for improvement in differentially private interactive proofs depends on the privacy parameter regime and model. Drawing on connections between privacy and replicability and privacy amplification techniques in the literature we show: 1. There exists a reduction from any one-round $(\varepsilon,δ)$-differentially private private-coin protocol to a differentially private AM protocol for the parameter regime $\varepsilon = O(1/\sqrt{s})$ and $δ= O(1/s^{5/2})$ with approximately the same privacy and sample and communication complexities. In the local model, this is relaxed to $\varepsilon = O(1/\sqrt{\log s})$ 2. However, when the privacy guarantee is very relaxed ($\varepsilon \in Ω(\log s)$), private coins indeed reduce sample and communication complexities. We also obtain a computationally efficient Merlin-Arthur proof for privately testing whether samples are drawn from a product distribution and prove that its sample complexity is optimal up to a $polylog N$ factor by reducing uniformity testing to independence testing with Boolean attributes and appealing to known lower bounds on sample complexity for private uniformity testing.

cs.DS · cs.CC · cs.LG

新论文 · v1arXiv:2611.13134

A Fast Algorithm for Subspace Convolution

Shlomo A. Perles, Omri Weinstein

原文摘要

A cornerstone result in Boolean lattice theory is the subset-zeta transform, which computes the $f$-weighted subset summation problem $(Z f)(B)=\sum_{A\subseteq B}f(A)$ for all $ B\subseteq[n]$ in $O(N \log N)$ additions instead of the naïve $O(3^n) = O(N^{\log_2 3})$, where $N=2^n$. This paper studies the algebraic analogue of this problem--the subspace summation problem--where subsets are replaced by linear subspaces in $\mathbb{F}_q^n$. Surprisingly, we show that this problem admits a similar $Θ_q(N_q \log N_q)$-time algorithm, where $N_q$ is the number of subspaces. This improves substantially (in both theory and practice) over lattice-based algorithms ([BHK+16, KKW16]), which are known to be optimal for addition-only algorithms over $\mathbb R$. We prove similar runtimes for inversion, rank-constrained sums and span convolution. We describe two main applications: Fast linear algebra on Grassmann graphs: Matrix--vector multiplication for arbitrary distance-invariant kernels on $N$-vertex Grassmann graphs in $O_q(N\log N)$ arithmetic operations, together with fast spectral projections and exact solutions of the corresponding linear systems. Graph coloring of low binary cut-rank graphs: An $n^{2^{r^2/4+O(1)}}$-time algorithm for computing the chromatic number and chromatic polynomial of an $n$-vertex graph, given a rank-decomposition of width $r$. We also give quantitative reductions from satisfiability and monotone constraint problems. Experiments show speedups in measured running time of up to $18$ over the covering-pair algorithm for the zeta transform, $190$ over Poisson summation for rank-constrained sums, and $22$ over the distance-matrix recurrence for Grassmann kernel multiplication. Lean 4 formalizations of the transform identities, arithmetic operation bounds, and graph-coloring constructions accompany the paper [PW26].

cs.DS · cs.CC

新论文 · v1arXiv:2611.12795

通过补全框架对Aaronson-Ambainis猜想的简短证明

A short proof of the Aaronson-Ambainis Conjecture via the completion framework

Thomas Huffstutler, David Miloschewsky, Supartha Podder

AI 速读 基于摘要

作者报告利用补全框架给出了Aaronson-Ambainis猜想的一个简短证明,并建立了基于经典对手测度的更一般界。

quant-ph · cs.CC

查看原文摘要

We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function $f$ is defined on a $δ$-fraction of all $n$-bit strings and have quantum query complexity $Q(f)$, then, for every $0<ε<1$, a deterministic algorithm computes $f$ correctly on at least a $1-ε$ fraction of its domain using $O( Q(f)^6 / (εδ)^2)$ queries. Our proof uses the completion framework and establishes a more general bound in terms of the classical adversary measure. The only result we use from Turturean's recent proof is a special case of his certificate inequality, for which we provide a self-contained proof. We also derive the stronger variant of the Aaronson-Ambainis Conjecture, the bounded-polynomial influence conjecture, from our main result in the appendix.

新论文 · v1arXiv:2611.12757

简洁无限时域Lyapunov与LQR值问题是BQP完全的

Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete

Mohamed Serry, Jun Liu

AI 速读 基于摘要

作者证明:以布尔电路简洁表示的无限时域Lyapunov值问题(SLV)是BQP难的,且更一般的简洁LQR值问题(SLQRV)有多项式时间量子算法,因此二者均为BQP完全。

quant-ph · cs.CC · eess.SY · math.OC

查看原文摘要

Fundamental tasks in linear systems analysis and control require evaluating infinite-horizon output energies for autonomous systems and optimal value functions for controlled systems. These quantities are characterized by Lyapunov and algebraic Riccati equations, respectively. In this work, we study promise problems for their evaluation when the system matrices are sparse and represented succinctly by Boolean circuits specifying their nonzero entries, with input length polynomial in the logarithm of the system dimension. For dissipative autonomous systems with coordinate-vector initial states, we define the succinct Lyapunov value problem (SLV). Its extension to linear-quadratic optimal control is the succinct LQR value problem (SLQRV). We prove that SLV is $\BQP$-hard: every problem in bounded-error quantum polynomial time ($\BQP$) reduces to it in polynomial time. We then establish that the more general SLQRV problem admits a quantum algorithm running in time polynomial in the succinct input length. Since SLV is a special case of SLQRV, both problems are $\BQP$-complete. Consequently, unless bounded-error probabilistic polynomial time coincides with $\BQP$, no classical randomized algorithm can solve either problem on all promised instances in time polynomial in the succinct input length.

新论文 · v1arXiv:2611.12746

EQP⊆IP 不相对化

$\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize

Sinan Oral, Supartha Podder

AI 速读 基于摘要

作者构造递归预言机 O 与一元语言 L,使 L 属于 EQP^O 但不属于 IP^O∪PH^O,从而把 BQP 与 IP 的预言机分离强化到精确量子计算。

quant-ph · cs.CC

查看原文摘要

We construct a recursive oracle $O$ and a unary language $L\in\mathsf{EQP}^O\setminus(\mathsf{IP}^O\cup\mathsf{PH}^O)$, strengthening the $\mathsf{BQP}$ versus $\mathsf{IP}$ oracle separation of Bouland et al. to exact quantum computation. The separation is based on a variant of the Forrelation problem in which the normalized correlation of one Boolean function with the Fourier transform of another is promised to be exactly $+1/2$ or $-1/2$. The main technical contribution is a repair method that constructs distributions supported on these exact levels while preserving the indistinguishability needed for the $\mathsf{IP}$ and $\mathsf{PH}$ lower bounds. A uniform polynomial-time quantum algorithm distinguishes the two cases with certainty using only three oracle queries.

新论文 · v1arXiv:2611.12714

Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

Sebastian Senge

原文摘要

We give quantum algorithms for exponential-time problems on $n$ vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time $O(1.3032^n)$, from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, $O(1.3100^n)$. The previous best bound in this model, to our knowledge, is $O(1.3231^n)$. (2) $k$-Colouring below the previous best bound for $k \in \{5, 7, 8, 9, 10, 11\}$ and $13 \le k \le 18$, from $O(1.4518^n)$ for $k = 5$ to $O(1.9233^n)$ for $k = 18$. (3) Dominating Set in $O(1.2235^n)$, against the previous $O(2^{n/2})$, Independent Dominating Set in $O(1.1583^n)$, and Edge Dominating Set and Minimum Maximal Matching in $O(1.1501^n)$. (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with $c^k$ nodes up to polynomial factors, the problem is solved in quantum time $(2 - 1/c)^{n/2}$ up to polynomial factors. This gives Feedback Vertex Set in $O(1.3081^n)$, Subset and Group Feedback Vertex Set in $O(1.3229^n)$, Cluster Vertex Deletion in $O(1.2033^n)$, 3-Hitting Set in $O(1.2405^n)$, Proper Interval Vertex Deletion in $O(1.3541^n)$, Multicut on Trees in $O(1.1647^n)$ and Min-Ones $d$-SAT in $O^*((2-1/d)^{n/2})$. (5) Quantum exponential-time approximations below the quantum exact bounds, such as a 1.1-approximation for Vertex Cover in $O(1.0555^n)$ and for Feedback Vertex Set in $O(1.2161^n)$. The colouring exponents for $k \ge 6$ come from an evaluation of a known reduction recursion, computed in floating point with a margin.

cs.DS · cs.CC · quant-ph