new

Get trending papers in your email inbox!

Subscribe

Daily Papers

byAK and the research community

Nov 20

A structure theorem for streamed information

We identify the free half shuffle algebra of Schützenberger (1958) with an algebra of real-valued functionals on paths, where the half shuffle emulates integration of a functional against another. We then provide two, to our knowledge, new identities in arity 3 involving its commutator (area), and show that these are sufficient to recover the Zinbiel and Tortkara identities of Dzhumadil'daev (2007). We use these identities to prove that any element of the free half shuffle algebra can be expressed as a polynomial over iterated areas. Moreover, we consider minimal sets of iterated integrals defined through the recursive application of the half shuffle on Hall trees. Leveraging the duality between this set of Hall integrals and classical Hall bases of the free Lie algebra, we prove using combinatorial arguments that any element of the free half shuffle algebra can be written uniquely as a polynomial over Hall integrals. We interpret this result as a structure theorem for streamed information, loosely analogous to the unique prime factorisation of integers, allowing to split any real valued function on streamed data into two parts: a first that extracts and packages the streamed information into recursively defined atomic objects (Hall integrals), and a second that evaluates a polynomial function in these objects without further reference to the original stream. The question of whether a similar result holds if Hall integrals are replaced by Hall areas is left as an open conjecture. Finally, we construct a canonical, but to our knowledge, new decomposition of the free half shuffle algebra as shuffle power series in the greatest letter of the original alphabet with coefficients in a sub-algebra freely generated by a new alphabet with an infinite number of letters. We use this construction to provide a second proof of our structure theorem.

  • 5 authors
·
Jul 29, 2023

Cylindric plane partitions, Lambda determinants, Commutants in semicircular systems

This thesis is divided into three parts. The first part deals with cylindric plane partitions. The second with lambda-determinants and the third with commutators in semi-circular systems. For more detailed abstract please see inside. Cylindric plane partitions may be thought of as a natural generalization of reverse plane partitions. A generating series for the enumeration of cylindric plane partitions was recently given by Borodin. The first result of section one is a new bijective proof of Borodin's identity which makes use of Fomin's growth diagram framework for generalized RSK correspondences. The second result is a (q,t)-analog of Borodin's identity which extends previous work by Okada in the reverse plane partition case. The third result is an explicit combinatorial interpretation of the Macdonald weight occurring in the (q,t)-analog using the non-intersecting lattice path model for cylindric plane partitions. Alternating sign matrices were discovered by Robbins and Rumsey whilst studying λ-determinants. In the second part of this thesis we prove a multi-parameter generalization of the λ-determinant, generalizing a recent result by di Francesco. Like the original λ-determinant, our formula exhibits the Laurent phenomenon. Semicircular systems were first introduced by Voiculescu as a part of his study of von Neumann algebras. In the third part of this thesis we study certain commutator subalgebras of the semicircular system. We find a projection matrix with an interesting self-similar structure. Making use of our projection formula we given an alternative, elementary proof that the semicircular system is a factor.

  • 1 authors
·
Oct 25, 2021

Faster Algorithms for Text-to-Pattern Hamming Distances

We study the classic Text-to-Pattern Hamming Distances problem: given a pattern P of length m and a text T of length n, both over a polynomial-size alphabet, compute the Hamming distance between P and T[i, ., . , i+m-1] for every shift i, under the standard Word-RAM model with Theta(log n)-bit words. - We provide an O(nm) time Las Vegas randomized algorithm for this problem, beating the decades-old O(n m log m) running time [Abrahamson, SICOMP 1987]. We also obtain a deterministic algorithm, with a slightly higher O(nm(log mloglog m)^{1/4}) running time. Our randomized algorithm extends to the k-bounded setting, with running time Obig(n+nk{m}big), removing all the extra logarithmic factors from earlier algorithms [Gawrychowski and Uzna\'{n}ski, ICALP 2018; Chan, Golan, Kociumaka, Kopelowitz and Porat, STOC 2020]. - For the (1+epsilon)-approximate version of Text-to-Pattern Hamming Distances, we give an O(epsilon^{-0.93}n) time Monte Carlo randomized algorithm, beating the previous O(epsilon^{-1}n) running time [Kopelowitz and Porat, FOCS 2015; Kopelowitz and Porat, SOSA 2018]. Our approximation algorithm exploits a connection with 3SUM, and uses a combination of Fredman's trick, equality matrix product, and random sampling; in particular, we obtain new results on approximate counting versions of 3SUM and Exact Triangle, which may be of independent interest. Our exact algorithms use a novel combination of hashing, bit-packed FFT, and recursion; in particular, we obtain a faster algorithm for computing the sumset of two integer sets, in the regime when the universe size is close to quadratic in the number of elements. We also prove a fine-grained equivalence between the exact Text-to-Pattern Hamming Distances problem and a range-restricted, counting version of 3SUM.

  • 4 authors
·
Oct 19, 2023

An Efficient Tester-Learner for Halfspaces

We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan (2023). In this model, a learner certifies that the accuracy of its output hypothesis is near optimal whenever the training set passes an associated test, and training sets drawn from some target distribution -- e.g., the Gaussian -- must pass the test. This model is more challenging than distribution-specific agnostic or Massart noise models where the learner is allowed to fail arbitrarily if the distributional assumption does not hold. We consider the setting where the target distribution is Gaussian (or more generally any strongly log-concave distribution) in d dimensions and the noise model is either Massart or adversarial (agnostic). For Massart noise, our tester-learner runs in polynomial time and outputs a hypothesis with (information-theoretically optimal) error opt + epsilon for any strongly log-concave target distribution. For adversarial noise, our tester-learner obtains error O(opt) + epsilon in polynomial time when the target distribution is Gaussian; for strongly log-concave distributions, we obtain O(opt) + epsilon in quasipolynomial time. Prior work on testable learning ignores the labels in the training set and checks that the empirical moments of the covariates are close to the moments of the base distribution. Here we develop new tests of independent interest that make critical use of the labels and combine them with the moment-matching approach of Gollakota et al. (2023). This enables us to simulate a variant of the algorithm of Diakonikolas et al. (2020) for learning noisy halfspaces using nonconvex SGD but in the testable learning setting.

  • 4 authors
·
Feb 28, 2023

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem

The algebraic diversity framework generalizes temporal averaging over multiple observations to algebraic group action on a single observation for second-order statistical estimation. The central open problem in this framework is group selection: given an M-dimensional observation with unknown covariance structure, find the finite group whose spectral decomposition best matches the covariance. Naive enumeration of all subgroups of the symmetric group S_M requires exponential time in M. We prove that this combinatorial problem reduces to a generalized eigenvalue problem derived from the double commutator of the covariance matrix, yielding a polynomial-time algorithm with complexity O(d^2M^2 + d^3), where d is the dimension of a generator basis. The minimum eigenvector of the double-commutator matrix directly constructs the optimal group generator in closed form, with no iterative optimization. The reduction is exact: the double-commutator minimum eigenvalue is zero if and only if the optimal generator lies in the span of the basis, and its magnitude provides a certifiable optimality gap when it does not. This problem does not appear in the standard catalogs of computational complexity (Garey and Johnson, 1979) and represents a new class linking group theory, matrix analysis, and statistical estimation. We establish connections to independent component analysis (JADE), structured matrix nearness problems, and simultaneous matrix diagonalization, and we show that the double-commutator formulation is the unique approach that is simultaneously polynomial-time, closed-form, and certifiable. We extend the framework to non-Abelian symmetry recovery via a Sequential GEVP with deflation, and add two identifiability theorems characterizing the commutant-lattice ambiguity and the dichotomy on whether Aut(R) recovers a generative subgroup or only a supergroup.

  • 1 authors
·
May 7

Non-simple Arrangements of Lines and Pseudolines with Many Triangles

We study affine arrangements of an even number n of lines and pseudolines with many triangles. For simple ones, Blanc's bound limits the number of triangular faces to lfloor n(n-5/2)/3rfloor. Adapting the Bartholdi-Blanc-Loisel doubling to the even case, we construct an infinite series of arrangements of n=6cdot2^t+2 (8,14,26,50,ldots) straight lines with two triple points and (n(n-5/2)+1)/3 triangles, one more than the simple bound allows. We obtain exhaustive enumerations of triangle-maximal pseudoline arrangements, simple or not, for even nle12. For n=6,8,10,12,14 the maximum number of triangles, for both lines and pseudolines, is 7,15,25,38,54; for n=8,12,14 every optimal arrangement has multiple points. All optimal arrangements for even nle12 are realizable by straight lines, except two arrangements of 10 pseudolines, which are not stretchable. For the odd value n=11, no arrangement with 33 triangles exists even with multiple points. We also obtain even arrangements by adding a line to odd ones. For nequiv2pmod 6 this again gives one triangle more than the simple bound, in pseudolines up to n=44 and in straight lines for n=20 and n=32. Doubling these pseudoline arrangements gives members of the series 18cdot2^t+2 and 30cdot2^t+2 with the same excess, up to n=146 and n=242, respectively; those with n=38 and n=74 are realizable by straight lines. These results lead us to conjecture that an arrangement of an even number n of pseudolines has at most lfloor n(n-2)/3rfloor-lfloor n/6rfloor triangles.

  • 2 authors
·
Nov 1

Weak-to-Strong Elicitation via Mismatched Wrong Drafts

We consider whether off-policy experience from a smaller, weaker model can elicit capability in a stronger learner that on-policy RL fine-tuning (e.g., GRPO) does not reach. We find that injecting mathematically wrong drafts from a smaller but more domain-trained model -- mismatched to the current problem -- into a stronger learner's GRPO context consistently outperforms standard on-policy GRPO on held-out MATH-500 and out-of-distribution AIME 2025/2026. Concretely, we use Mathstral-7B as the learner, Qwen2.5-Math-1.5B as the draft model, 8.8K Level 3--5 MATH problems (with MATH-500 held out), and train with Dr. GRPO. Mismatch is an active ingredient: shuffling drafts to mismatched problems while holding everything else constant yields +1.62pp on MATH-500 (greedy pass@1) over the matched-wrong variant (n=10 seeds, p=0.0015, Welch's t). In fact, the mismatched-wrong variant leads all other variants we tested on MATH-500 across both greedy pass@1 and sampling pass@k. On out-of-distribution AIME 2025 and 2026, the mismatched-wrong variant uniquely lifts pass@k above both Mathstral-7B (in its native [INST] format) and the Qwen2.5-Math-1.5B draft model at every sample budget from k=1 to k=1024 across 2 seeds (+14.2pp on 2025 and +9.0pp on 2026 at pass@1024 over Mathstral-7B), and at pass@1024 also leads no-draft, matched-wrong, and mismatched-correct variants on both years. All variants use the same prompt with no draft injection at test time. The recipe -- trained on a single GPU with no SFT, no reward models, no synthesized data, and no produce-critique-revise inner loop -- reaches 71.98% MATH-500 on Mathstral-7B-v0.1, the highest published result on this model to our knowledge, surpassing the heavier WizardMath pipeline at 70.9% on full MATH (SFT + PPO with process/instruction reward models).

  • 1 authors
·
May 16

Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests

We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomials. For a matroid of rank k on a ground set of n elements, or more generally distributions associated with log-concave polynomials of homogeneous degree k on n variables, we show that the down-up random walk, started from an arbitrary point in the support, mixes in time O(klog k). Our bound has no dependence on n or the starting point, unlike the previous analyses [ALOV19,CGM19], and is tight up to constant factors. The main new ingredient is a property we call approximate exchange, a generalization of well-studied exchange properties for matroids and valuated matroids, which may be of independent interest. In particular, given function μ: {[n] choose k} to R_{geq 0}, our approximate exchange property implies that a simple local search algorithm gives a k^{O(k)}-approximation of max_{S} μ(S) when μ is generated by a log-concave polynomial, and that greedy gives the same approximation ratio when μ is strongly Rayleigh. As an application, we show how to leverage down-up random walks to approximately sample random forests or random spanning trees in a graph with n edges in time O(nlog^2 n). The best known result for sampling random forest was a FPAUS with high polynomial runtime recently found by ALOV19, CGM19. For spanning tree, we improve on the almost-linear time algorithm by [Sch18]. Our analysis works on weighted graphs too, and is the first to achieve nearly-linear running time for these problems.

  • 5 authors
·
Apr 10, 2021

CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)

This is the third paper of the CayleyPy project applying artificial intelligence to problems in group theory. We announce the first public release of CayleyPy, an open source Python library for computations with Cayley and Schreier graphs. Compared with systems such as GAP and Sage, CayleyPy handles much larger graphs and performs several orders of magnitude faster. Using CayleyPy we obtained about 200 new conjectures on Cayley and Schreier graphs, focused on diameters and growth. For many Cayley graphs of symmetric groups Sn we observe quasi polynomial diameter formulas: a small set of quadratic or linear polynomials indexed by n mod s. We conjecture that this is a general phenomenon, giving efficient diameter computation despite the problem being NP hard. We propose a refinement of the Babai type conjecture on diameters of Sn: n^2/2 + 4n upper bounds in the undirected case, compared to previous O(n^2) bounds. We also provide explicit generator families, related to involutions in a square with whiskers pattern, conjectured to maximize the diameter; search confirms this for all n up to 15. We further conjecture an answer to a question posed by V M Glushkov in 1968 on directed Cayley graphs generated by a cyclic shift and a transposition. For nilpotent groups we conjecture an improvement of J S Ellenberg's results on upper unitriangular matrices over Z/pZ, showing linear dependence of diameter on p. Moreover. Some conjectures are LLM friendly, naturally stated as sorting problems verifiable by algorithms or Python code. To benchmark path finding we created more than 10 Kaggle datasets. CayleyPy works with arbitrary permutation or matrix groups and includes over 100 predefined generators. Our growth computation code outperforms GAP and Sage up to 1000 times in speed and size.

  • 49 authors
·
Sep 23, 2025

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum

We study circuits for computing depth-2 linear transforms defined by Kronecker power matrices. Recent works have improved on decades-old constructions in this area using a new ''rebalancing'' approach [Alman, Guan and Padaki, SODA'23; Sergeev'22], but it was unclear how to apply this approach optimally. We find that Strassen's theory of asymptotic spectra can be applied to capture the design of these circuits. In particular, in hindsight, we find that the techniques of recent work on rebalancing were proving special cases of the duality theorem, which is central to Strassen's theory. We carefully outline a collection of ''obstructions'' to designing small depth-2 circuits using a rebalancing approach, and apply Strassen's theory to show that our obstructions are complete. Using this connection, combined with other algorithmic techniques, we give new improved circuit constructions as well as other applications, including: - The N times N disjointness matrix has a depth-2 linear circuit of size O(N^{1.2495}) over any field. This also yield smaller circuits for many families of matrices using reductions to disjointness. - The Strong Exponential Time Hypothesis implies an N^{1 + Ω(1)} size lower bound for depth-2 linear circuits computing the Walsh--Hadamard transform (and the disjointness matrix with a technical caveat), and proving a N^{1 + Ω(1)} depth-2 size lower bound would also imply breakthrough threshold circuit lower bounds. - The Orthogonal Vectors (OV) problem in moderate dimension d can be solved in deterministic time O(n cdot 1.155^d), derandomizing an algorithm of Nederlof and Węgrzycki [STOC'21], and the counting problem can be solved in time O(n cdot 1.26^d), improving an algorithm of Williams [FOCS'24] which runs in time O(n cdot 1.35^d).

  • 2 authors
·
Sep 16, 2025

Operator-language Feynman rules for driven-dissipative quantum systems: from mean field to non-Gaussian photon correlations

We construct Feynman rules for Lindblad master equations in the operator language of quantum optics: a fixed algebra of elementary operator moves and closed-form propagators for perturbation theory about an exactly solvable, in most cases Gaussian, generator. The expansion separates into a kinematic part (the shift algebra on the Wick-ordered eigenoperators O_{mn}=:(c^dagger)^m c^n:, from which the vertex table for a specified interaction is assembled) and a dynamical part that enters only through the resolvent of the unperturbed generator, diagonal and additive for any stable, diagonalizable Gaussian L_0, including thermal and squeezed reservoirs and correlated decay, and equally available for a two-level emitter, driven or undriven. In the driven Kerr cavity the loop expansion is the semiclassical expansion and the series is asymptotic. In a strongly driven two-level atom, dressed lines replace a series of finite radius by one accurate deep into saturation, one line per Mollow component. For Kerr rings and chains the cost is polynomial in the number of sites at fixed perturbative order. On a three-site ring the diagrams recover the non-Gaussian part of the three-photon correlation that the Gaussian cumulant closure lacks; carried to tenth order they give the smallest g^{(3)} error of the methods compared for Uleq0.25κ at a cost below that of a fourth-order closure, and third- and fourth-order closures are more accurate at moderate coupling. The same rules, extended to the counting-field-tilted generator, give the photon-counting cumulants of a disordered eight-site chain beyond direct diagonalization; quantum-jump trajectories at three couplings agree with them to within 1.6 standard errors, within one at the strongest coupling, where they place the third cumulant six standard errors above the Gaussian value.

  • 3 authors
·
Sep 29

Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm

In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon's period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive. In this paper, we introduce a new quantum algorithm which uses Simon's subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search with Grover's algorithm. In particular, we are able to break the Even-Mansour construction in quantum time O(2^{n/3}), with O(2^{n/3}) classical queries and O(n^2) qubits only. In addition, we improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity. Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover's algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure. We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.

  • 5 authors
·
Feb 26, 2020

A Benchmark for Math Misconceptions: Bridging Gaps in Middle School Algebra with AI-Supported Instruction

This study introduces an evaluation benchmark for middle school algebra to be used in artificial intelligence(AI) based educational platforms. The goal is to support the design of AI systems that can enhance learner conceptual understanding of algebra by taking into account their current level of algebra comprehension. The data set comprises 55 misconceptions about algebra, common errors, and 220 diagnostic examples identified in previous peer-reviewed studies. We provide an example application using a large language model, observing a range of precision and recall scores depending on the topic and experimental setup that reaches 83.9% when including educator feedback and restricting it by topic. We found that topics such as ratios and proportions prove as difficult for LLMs as they are for students. We included a human assessment of LLMs results and feedback from five middle school math educators on the clarity and occurrence of misconceptions in the dataset and the potential use of AI in conjunction with the dataset. Most educators (80% or more) indicated that they encounter these misconceptions among their students, suggesting the relevance of the data set to teaching middle school algebra. Despite varying familiarity with AI tools, four out of five educators expressed interest in using the data set with AI to diagnose student misconceptions or train teachers. The results emphasize the importance of topic-constrained testing, the need for multimodal approaches, and the relevance of human expertise to gain practical insights when using AI for human learning.

  • 3 authors
·
Dec 4, 2024

Rethinking Multi-User Communication in Semantic Domain: Enhanced OMDMA by Shuffle-Based Orthogonalization and Diffusion Denoising

Inter-user interference remains a critical bottleneck in wireless communication systems, particularly in the emerging paradigm of semantic communication (SemCom). Compared to traditional systems, inter-user interference in SemCom severely degrades key semantic information, often causing worse performance than Gaussian noise under the same power level. To address this challenge, inspired by the recently proposed concept of Orthogonal Model Division Multiple Access (OMDMA) that leverages semantic orthogonality rooted in the personalized joint source and channel (JSCC) models to distinguish users, we propose a novel, scalable framework that eliminates the need for user-specific JSCC models as did in original OMDMA. Our key innovation lies in shuffle-based orthogonalization, where randomly permuting the positions of JSCC feature vectors transforms inter-user interference into Gaussian-like noise. By assigning each user a unique shuffling pattern, the interference is treated as channel noise, enabling effective mitigation using diffusion models (DMs). This approach not only simplifies system design by requiring a single universal JSCC model but also enhances privacy, as shuffling patterns act as implicit private keys. Additionally, we extend the framework to scenarios involving semantically correlated data. By grouping users based on semantic similarity, a cooperative beamforming strategy is introduced to exploit redundancy in correlated data, further improving system performance. Extensive simulations demonstrate that the proposed method outperforms state-of-the-art multi-user SemCom frameworks, achieving superior semantic fidelity, robustness to interference, and scalability-all without requiring additional training overhead.

  • 5 authors
·
Jul 27, 2025

Properties of tensorial free cumulants

In the past two years, several points of view have been proposed to address the question of the generalization of the theory of free probability to random tensors with different invariances, and it is unclear at this point whether they lead to the same notions of tensorial free cumulants and freeness. One way to approach this problem, developed by Collins, Gurau and the second named author for local unitary invariant random tensors, relies on finite size quantities involving averages over the invariance group, and whose asymptotics naturally possess the properties expected for tensorial generalizations of free cumulants of arbitrary orders. At this point, this approach has only been carried out for certain distributions, and for a subset of the moments that define such theories, and a more systematic and exhaustive study is lacking. This is the program initiated in this paper: we link this approach to the one proposed by Nechita and Park; extend a number of their results as well as those of the aforementioned paper to arbitrary orders of fluctuations, thereby generalizing higher order free cumulants; push further the study of distributions with larger invariance groups; detail the link with the asymptotics of the free-energies of the tensor HCIZ and BGW integrals; and provide formulae for tensorial free cumulants of products of tensors. Another important question is that of the definition of concrete distributions whose tensorial free-cumulants take non-trivial values. We compute the tensorial free cumulants for Gaussian random tensors with non-trivial covariances, and show that they provide such examples.

  • 2 authors
·
May 2

A Reproducible Software Workflow for Unanchored Approximate MUB Optimization: A Case Study in Dimension Six

We present a reproducible, parameter-driven software workflow for optimizing approximate mutually unbiased basis (AMUB) configurations in arbitrary dimensions d using a Lie-algebra unitary parameterization. The workflow is designed for portable execution across CPU, Apple MPS, CUDA-capable GPU, and HPC backends, using a Taylor-series matrix exponential layer as an accelerator compatibility pathway. As a dimension-six case study, we optimize unanchored configurations across 100 random seeds for basis counts n = 3, 4, 5, 6 in complex128 and complex64 arithmetic. The workflow recovers exact three-basis configurations, identifies a recurrent four-basis partial-exact hub-and-triangle structure, and finds no near-exact pairs for n = 5 or n = 6 in the reported campaigns under the primary tolerance. As a hardware-execution check, we embed the representative d = 6, n = 4 transition unitaries into three-qubit 8x8 unitaries and execute the resulting circuits on the 156-qubit Heron processor ibm-marrakesh using subspace post-selection. The measured QPU pairwise losses are dominated by a hardware and compilation noise floor of approximately 0.02-0.08, associated with compiled circuits averaging 37 native CZ gates, which obscures the distinction between classically near-exact and defective pairs. The results provide a reproducible computational framework for exploring AMUB landscapes, together with an initial assessment of the challenges involved in executing optimized dimension-six unitaries on current quantum hardware.

  • 3 authors
·
Jul 11

Improved Bounds for the Bilu--Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials

The Bilu--Linial conjecture asks whether every finite d-regular graph with d geq 2 admits an edge signing σ whose signed adjacency matrix A_σ has spectral radius at most 2d-1. We prove that every signing meeting the mixed-root condition r_{A_σ}leq2(d-1) satisfies \[ ρ(A_σ) < 3+\sqrt5{2}d-1, \] where r_{A_σ} is the largest root of the mixed determinantal polynomial χ[A_σ,-A_σ]. The interlacing theorem of Ravichandran and Srivastava guarantees a signing satisfying the mixed-root condition, so our result improves the coefficient 2sqrt2 in their two-sided spectral bound. In the proof, we construct a positive matrix-valued probability measure supported on the roots of χ[A_σ,-A_σ]. The second moment gives a simple matrix inequality A_σ^2 + dI preceq 4r_{A_σ}^2I, which yields a preliminary coefficient 7. Estimates for the fourth moment use information about short walks to obtain the coefficient (3+5)/2. With more graph structural assumptions, the coefficient improves to sqrt6 for triangle-free graphs and to (5+3sqrt5)/2 for graphs of girth at least five. As a result of independent interest, we extend the construction to χ[A_1,ldots,A_k] for Hermitian matrices A_1,ldots,A_k with zero diagonal, and compute the first two moments explicitly. Finally, an explicit signing of K_8 shows that the mixed-root condition alone cannot guarantee a coefficient below (4+sqrt5)/sqrt6.

  • 2 authors
·
Sep 13

Exact Learning of Permutations for Nonzero Binary Inputs with Logarithmic Training Size and Quadratic Ensemble Complexity

The ability of an architecture to realize permutations is quite fundamental. For example, Large Language Models need to be able to correctly copy (and perhaps rearrange) parts of the input prompt into the output. Classical universal approximation theorems guarantee the existence of parameter configurations that solve this task but offer no insights into whether gradient-based algorithms can find them. In this paper, we address this gap by focusing on two-layer fully connected feed-forward neural networks and the task of learning permutations on nonzero binary inputs. We show that in the infinite width Neural Tangent Kernel (NTK) regime, an ensemble of such networks independently trained with gradient descent on only the k standard basis vectors out of 2^k - 1 possible inputs successfully learns any fixed permutation of length k with arbitrarily high probability. By analyzing the exact training dynamics, we prove that the network's output converges to a Gaussian process whose mean captures the ground truth permutation via sign-based features. We then demonstrate how averaging these runs (an "ensemble" method) and applying a simple rounding step yields an arbitrarily accurate prediction on any possible input unseen during training. Notably, the number of models needed to achieve exact learning with high probability (which we refer to as ensemble complexity) exhibits a linearithmic dependence on the input size k for a single test input and a quadratic dependence when considering all test inputs simultaneously.

  • 3 authors
·
Feb 23, 2025

Evaluating and Improving Tool-Augmented Computation-Intensive Math Reasoning

Chain-of-thought prompting~(CoT) and tool augmentation have been validated in recent work as effective practices for improving large language models~(LLMs) to perform step-by-step reasoning on complex math-related tasks. However, most existing math reasoning datasets may be not able to fully evaluate and analyze the ability of LLMs in manipulating tools and performing reasoning, as they may only require very few invocations of tools or miss annotations for evaluating intermediate reasoning steps. To address the issue, we construct CARP, a new Chinese dataset consisting of 4,886 computation-intensive algebra problems with formulated annotations on intermediate steps. In CARP, we test four LLMs with CoT prompting, and find that they are all prone to make mistakes at the early steps of the solution, leading to wrong answers. Based on this finding, we propose a new approach that can deliberate the reasoning steps with tool interfaces, namely DELI. In DELI, we first initialize a step-by-step solution based on retrieved exemplars, then iterate two deliberation procedures that check and refine the intermediate steps of the generated solution, from the perspectives of tool manipulation and natural language reasoning, until obtaining converged solutions or reaching the maximum turn. Experimental results on CARP and six other datasets show that the proposed DELI mostly outperforms competitive baselines, and can further boost the performance of existing CoT methods. Our data and code are available in https://github.com/RUCAIBox/CARP.

  • 7 authors
·
Jun 4, 2023

An analytical framework for the Levine hats problem: new strategies, bounds and generalizations

We study the Levine hat problem, a classic combinatorial puzzle introduced by Lionel Levine in 2010. This problem involves a game in which n geq 2 players, each seeing an infinite stack of hats on each of their teammates' heads but not on their own, must simultaneously guess the index of a black hat on their own stack. If one of the players fails to do so, the team loses collectively. The players must therefore come up with a good strategy before the game starts. While the optimal winning probability V_{n} remains unknown even for n=2, we make three key advances. First, we develop a novel geometric framework for representing strategies through measurable functions, providing a new expression of V_{n} and a unified treatment of the game for finite and for infinite stacks via integral formulations. Secondly, we construct a new strategy K_{5} that reaches the conjectured optimal probability of victory : 0.35. We also show that K_{5} is part of a larger class of strategies that allow us to improve current bounds and resolve conjectured inequalities. Finally, we introduce and entirely solve a continuous generalization of the problem, demonstrating that extending to uncountable hat stacks increases the optimal winning probability to exactly 1/2. This generalization naturally leads to a broader and smoother strategic framework, within which we also describe how to compute optimal responses to a range of strategies.

  • 5 authors
·
Aug 3, 2025

Qin's Algorithm, Continued Fractions and 2-dimensional Lattices

In his celebrated book "Mathematical Treatise in Nine Sections" of 1247, Qin, Jiushao described the Chinese remainder theorem with great detail and generality. He also gave a method for computing modular inverse under the name of "DaYan deriving one". Historical significance of DaYan deriving one method has been well studied. In this paper, we investigate its modern mathematical nature from the perspectives of number theory and algorithm. One of the remarkable features of Qin's algorithm is that it keeps a state of four variables in a matrix form. Its choice of variables and layout provide natural ways of connecting several important mathematical concepts. An invariant about the state is also observed which provides a convenient yet powerful tool in proving several important mathematical results. The paper first explains Qin's algorithm and proves some of its properties. Then the connection with continued fractions is examined, the results show that the states of Qin's algorithm contain rich information about continued fractions and some classical arguments can be derived easily. The last part of the paper discusses a family of 2-dimensional lattices of number theoretic significance by proving that the shortest vectors of these lattices can be obtained from the states of Qin's algorithm. This result is surprising in that a shortest lattice vector is found in a well-regulated set. A method of computing such shortest vectors is proposed.ed.

  • 2 authors
·
Nov 6, 2023