Compare Papers
Paper 1
Pseudorandom Function from Learning Burnside Problem
Dhiraj K. Pandey, Antonio R. Nicolosi
- Year
- 2025
- Journal
- Mathematics
- DOI
- 10.3390/math13071193
- arXiv
- -
We present three progressively refined pseudorandom function (PRF) constructions based on the learning Burnside homomorphisms with noise (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>B</mi><mi>n</mi></msub></semantics></math></inline-formula>-LHN) assumption. A key challenge in this approach is error management, which we address by extracting errors from the secret key. Our first design, a direct pseudorandom generator (PRG), leverages the lower entropy of the error set (<i>E</i>) compared to the Burnside group (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>B</mi><mi>r</mi></msub></semantics></math></inline-formula>). The second, a parameterized PRG, derives its function description from public parameters and the secret key, aligning with the relaxed PRG requirements in the Goldreich–Goldwasser–Micali (GGM) PRF construction. The final indexed PRG introduces public parameters and an index to refine efficiency. To optimize computations in Burnside groups, we enhance concatenation operations and homomorphisms from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>B</mi><mi>n</mi></msub></semantics></math></inline-formula> to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>B</mi><mi>r</mi></msub></semantics></math></inline-formula> for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≫</mo><mi>r</mi></mrow></semantics></math></inline-formula>. Additionally, we explore algorithmic improvements and parallel computation strategies to improve efficiency.
Open paperPaper 2
Optimizing and benchmarking the computation of the permanent of general matrices
Cassandra Masschelein, Michelle Richer, Paul W. Ayers
- Year
- 2025
- Journal
- arXiv preprint
- DOI
- arXiv:2510.03421
- arXiv
- 2510.03421
Evaluating the permanent of a matrix is a fundamental computation that emerges in many domains, including traditional fields like computational complexity theory, graph theory, many-body quantum theory and emerging disciplines like machine learning and quantum computing. While conceptually simple, evaluating the permanent is extremely challenging: no polynomial-time algorithm is available (unless $\textsc{P} = \textsc{NP}$). To the best of our knowledge there is no publicly available software that automatically uses the most efficient algorithm for computing the permanent. In this work we designed, developed, and investigated the performance of our software package which evaluates the permanent of an arbitrary rectangular matrix, supporting three algorithms generally regarded as the fastest while giving the exact solution (the straightforward combinatoric algorithm, the Ryser algorithm, and the Glynn algorithm) and, optionally, automatically switching to the optimal algorithm based on the type and dimensionality of the input matrix. To do this, we developed an extension of the Glynn algorithm to rectangular matrices. Our free and open-source software package is distributed via Github, at https://github.com/theochem/matrix-permanent.
Open paper