We introduce a new family of propositional proof systems, denoted $\langle EF, R \rangle$, for an arbitrary TFNP search problem $R$. Informally, a refutation of a CNF formula $F$ in $\langle EF, R \rangle$ is given by a polynomial-time mapping reduction from the false-clause search problem ${\mathrm{Search}}_F$ to $R$, combined with an Extended Frege proof that the reduction is correct. These new…

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations (“separating modules,” which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We characterize the power of this…

The Hamiltonian Cycle polynomial, denoted as $HC_n$, is defined to be the sum of the weighted Hamiltonian Cycles in an $n$-vertex complete digraph, with vertices labeled $1$ to $n$ and edges weighted by formal variables $x_{i,j}$. The Permanent and $HC$, defined as the family $\{HC_n | \ n \geq 1\}$, were studied by Valiant (STOC 1979), with the former shown to be VNP-complete over all fields of…

I’ve been hesitating in writing up a blog post about my latest preprint, “Minimum-weight Steiner triangulation of convex polygons
requires interior Steiner points” (with my student Zahra Hadizadeh, arXiv:2606.25302, to appear at CCCG) because, despite being a completely concrete two-dimensional construction, its exponential scale makes it difficult to visualize. In the paper we included an…

Authors: Somnath Bhattacharjee, Rishabh Kothary, Shanthanu S. Rai, Shubhangi Saraf

We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results. 1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a…

We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results.

1. We give a deterministic polynomial-time algorithm which takes as input an $n$-variate $s$-sparse polynomial $f$ of bounded individual degree $d$ and outputs a list of circuits which contains all factors of $f$, although there might be additional…

Authors: Qisheng Wang

We consider the problem of estimating the fidelity of an unknown quantum state to a known reference state to within additive error $\varepsilon$. We show that the sample complexity is $O(r^2/\varepsilon^2)$ with optimal $\varepsilon$-dependence when the reference state is of rank $r$, improving the previous best $O(r^2\log^2(1/\varepsilon)/\varepsilon^4)$ due to Utsumi,…

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think solely about the problem and potential solutions, and more importantly block out all other thoughts and even lose track of time. Mathematicians don't own the zone, actors, musicians, athletes and many others have their own version of the zone. But for math, when working…

Authors: Minghao Chen, Jiale Zheng

Spectral filtering recently delivered substantial pruning for \emph{static} subgraph matching: Laplacian interlacing rejects candidates whose neighborhoods cannot host the query. We study whether such aggregate structural tests can accelerate \emph{continuous} subgraph matching (CSM) over dynamic graphs, and answer in three parts. First, lazily maintained…

Authors: Nicolas Gast, Bruno Gaujal, Adrien Obrecht

In this paper we consider a M/G/1 queue for which we want to minimize the expected response time. We show how to compute indices from $n$ samples of the job size distribution such that the corresponding index policy is asymptotically optimal as $n$ grows. This construction is based on a discretization of the bounded support of the job size…

Authors: Juul Sanders, Sebastiaan Brand, Arend-Jan Quist, Tim Coopmans

The decision diagram (DD) data structure enables fast linear-algebra calculations by bringing vectors into a normal form and subsequently merging equivalent ones, yielding a minimally-sized DD modulo the equivalence relation. A fruitful application area is quantum-circuit simulation, where the vectors represent quantum…

Authors: Sanjeev Khanna, Aaron Putterman, Junkai Song

We settle the classic question of the parallel complexity of computing a matroid basis, as first posed in the seminal work of Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988). Our algorithm runs in $O(n^{1/3}\log^{1/3}n)$ rounds, matching the lower bound of KUW up to a $\log^{2/3}(n)$ factor.

Authors: Barbara Giunti, Elizabeth Munch

In this paper, we provide a new construction for studying parameterized persistence, called a canopy. We give two versions of this construction: the A-canopy, retaining all information about points on the diagonal of the persistence diagram; and the D-canopy, encoding the information of the "standard" persistence diagram. We do this by making a simple…

Authors: Fabien Feschet, Jacques-Olivier Lachaud

Full convexity is an interesting alternative to classical digital convexity since it guarantees connectedness and even simple connectedness in digital spaces Z d , for any dimension d. This paper aims at giving a better understanding of the monotonicity properties of fully convex digital sets, since earlier works showed that the question was…

Authors: Louis Desruisseaux, Simon Ducharme, Gurleen Padda, Dave Touchette

For many information processing tasks, de Finetti-style theorems can often simplify the analysis in worst-case input scenarios for which the task exhibits some permutation-invariance symmetry, as they can allow for a reduction from an analysis on worst-case inputs to that of i.i.d. inputs. If further information is…

Authors: Jie Wang

Wang~\cite{Wang2026} introduced the Stochastic-Oracle Turing Machine (SOTM) framework and defined token complexity as the minimum expected cost of interacting with a stochastic oracle needed to attain a specified solution quality for a task. This paper develops an analogous notion for certifying the reliability of a stochastic oracle on a given domain. Certification token…

Authors: Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, Christian Schindelhauer

We establish that the two-dimensional ray tracing problem with thin lenses and plane mirrors is Turing-complete, thereby resolving an open question posed by Reif et al. in 1994 as to whether three-dimensional space is necessary for computational universality in optical systems. To this end, we consider the…

Authors: Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro

We prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates of a fixed test, and another controlling large families of Fourier-pseudorandom tests. Two motivating applications…

Authors: Michael T. M. Emmerich

We study fixed-cardinality subset selection for the exact integral bi-objective $R_2$ indicator with a uniform continuum of weighted Tchebycheff scalarizing functions. The indicator measures the area under the lower envelope of scalarizing losses over weight space, rather than a finite sample average over weight vectors. For a sorted bi-objective Pareto-front…

Authors: Annesha Sen, Shivam Singh, S. P. Tiwari

Mapper is a well-known tool in topological data analysis, which visualizes and summarizes high-dimensional data. However, its output is sensitive to choices of lens functions, cover parameters, and clustering strategies, making evaluation challenging. Most works that have attempted to evaluate the Mapper algorithm have done so visually. In…

Authors: Annesha Sen, Shivam Singh, S. P. Tiwari

Topological Data Analysis uses tools from algebraic topology to study the shape and structure of data. The Mapper algorithm provides a graph-based summary of high-dimensional datasets by combining a filter function, a cover of the filter range, and clustering on the corresponding pullback sets. Several variants of Mapper have been proposed,…

Authors: Mithil Ramteke

We study exact nonnegative matrix factorization (NMF) of small exact-rank-r matrices via a cone-ray pipeline combining the truncated SVD, the polyhedral cone of nonnegative preimages, the Double Description Method (DDM, via Fukuda's cddlib), and an alternating linear program (alt-LP) for slack minimisation. Under a uniform-support restriction the factorisation…

Authors: Liyan Chen, Matthew M. Hong, Yael Tauman Kalai, Zoe Xi

We show that every language in PSPACE decidable by a Turing machine in time $T(n)=n^{O(\log n)}$ admits a doubly efficient interactive proof system: the prover runs in time polynomial in T(n), and the verifier runs in time polynomial in n. This extends the best previously known regime for such proof systems from…

Authors: Tianhang Lu, Runtian Ren, Shengcai Liu

This paper studies learning-augmented online weighted vertex cover with advice and a parameter $λ\in (0,1)$. We consider two graph cases: bipartite graphs and general graphs. In both settings, the online algorithm must maintain a feasible vertex cover under irrevocable decisions. We show that these problems admit the same…

Authors: Chenyuan Jia, Qingqing Peng, Ke Liu, Guanghui Wang, Guiying Yan

The minimum distance problem (MDP) for low-density parity-check (LDPC) codes is a central problem in coding theory and is closely related to the analysis of low-weight codewords and error-floor behavior. Although the unrestricted MDP is computationally intractable, its complexity under degree constraints that commonly…

Authors: Avishay Tal, Weiqiang Yuan

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$…

Authors: Eduardo Yuji Sakabe, Felipe S. Abrahão, Santiago Hernández-Orozco, Ricardo Gudwin, Hector Zenil

The Block Decomposition Method (BDM) was introduced as an alternative to popular lossless compression methods such as LZW for estimating algorithmic complexity from the principles of algorithmic probability and classical information theory. It extends the Coding Theorem Method (CTM) from…

Authors: Ming Yang

Classical simulations of quantum correlations can fail because no low-communication local hidden-variable model exists, or because no single noncontextual hidden state can explain all compatible measurement contexts. This manuscript studies a third regime: genuine global Kochen-Specker contextuality, where local subsystems are noncontextual and the tested multipartite…

(All references in this blog post can be found in the main article the post is about which is here.)

Recall that \\(R(s,k) \\) is the least \\(n\\) so that, for all 2-colorings of the edges of \\(K_n\\), there is either a RED \\(s\\)-clique or a BLUE \\(k\\)-clique.

\\(R(k,k)\\) has been well studied and is often called \\(R(k)\\).

However, today we are concerned with \\(R(s,k)\\) \\(s\\) is…

On Friday, Midjourney, a generative AI company best known for automatically creating DeviantArt images from text prompts, announced it was pivoting to medicine. Their web copy opens with blunt honesty: “Today we’re gonna announce something a little weird and a little crazy, but also spectacular and filled with hope.” What follows is a cinematic trailer straight out of Ridley Scott’s Alien…