Publications related to Integer factorization

Additive and geometric transversality of fractal sets in the integers

By juxtaposing ideas from fractal geometry and dynamical systems, Furstenberg proposed a series of conjectures in the late 1960's that explore the relationship between digit expansions with respect to multiplicatively independent bases. In this work, we in ...

2024

Toroidal families and averages of L-functions, I

Philippe Michel

We initiate the study of certain families of L-functions attached to characters of subgroups of higher-rank tori, and of their average at the central point. In particular, we evaluate the average of the values L( 2 1 , chi a )L( 21 , chi b ) for arbitrary ...

Polish Acad Sciences Inst Mathematics-Impan2024

A NEW PROOF OF THE ERDOS-KAC CENTRAL LIMIT THEOREM

Thomas Mountford, Michael Cranston

In this paper we use the Riemann zeta distribution to give a new proof of the Erdos-Kac Central Limit Theorem. That is, if zeta(s) = Sigma(n >= 1) (1)(s)(n) , s > 1, then we consider the random variable X-s with P(X-s = n) = (1) (zeta) ( ...

Amer Mathematical Soc2023

Extractable Witness Encryption for the Homogeneous Linear Equations Problem

Serge Vaudenay, Bénédikt Minh Dang Tran

Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption construc ...

Springer2023

On the Use of the Generalized Littlewood Theorem Concerning Integrals of the Logarithm of Analytical Functions for the Calculation of Infinite Sums and the Analysis of Zeroes of Analytical Functions

Serguei Sekatski

Recently, we have established and used the generalized Littlewood theorem concerning contour integrals of the logarithm of an analytical function to obtain a few new criteria equivalent to the Riemann hypothesis. Here, the same theorem is applied to calcul ...

MDPI2023

Revisiting Offline Compression: Going Beyond Factorization-based Methods for Transformer Language Models

Karl Aberer, Rémi Philippe Lebret, Mohammadreza Banaei

Recent transformer language models achieve outstanding results in many natural language processing (NLP) tasks. However, their enormous size often makes them impractical on memory-constrained devices, requiring practitioners to compress them to smaller net ...

Assoc Computational Linguistics-Acl2023

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

BLOOM: Bimodal Lattice One-out-of-Many Proofs and Applications

Ngoc Khanh Karol Nguyen

We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Ly ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Recoloring subgraphs of K-2n for sports scheduling

Dominique de Werra

The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. Thi ...

ELSEVIER2021

A hierarchical preconditioner for wave problems in quasilinear complexity

Jan Sickmann Hesthaven, Boris Bonev

The paper introduces a novel, hierarchical preconditioner based on nested dissection and hierarchical matrix compression. The preconditioner is intended for continuous and discontinuous Galerkin formulations of elliptic problems. We exploit the property th ...

2022

Paths in pseudorandom graphs and applications

Van Thang Pham

Let G = (V, E) be an (n, d, lambda)-graph. In this paper, we give an asymptotically tight condition on the size of U subset of V such that the number of paths of length k in U is close to the expected number for arbitrary integer k >= 1. More precisely, we ...

CHARLES BABBAGE RES CTR2020

Polynomial Evaluation on Superscalar Architecture, Applied to the Elementary Function e(x)

Felix Schürmann, Francesco Cremonesi, Timothée Ewart, Fabien Jonathan Delalondre

The evaluation of small degree polynomials is critical for the computation of elementary functions. It has been extensively studied and is well documented. In this article, we evaluate existing methods for polynomial evaluation on superscalar architecture. ...

2020

A simple proof for a forbidden subposet problem

Abhishek Methuku

The poset Y-k,Y-2 consists of k + 2 distinct elements x(1), x(2), ..., x(k), y(1), y(2), such that x(1)

ELECTRONIC JOURNAL OF COMBINATORICS2020

Minimal graphs for 2-factor extension

Dominique de Werra

Let G = (V, E) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge uv, G + uv has a 2-factor F that contains uv. We are interested in the following: Given a positive integer n = vertical bar V vertical b ...

ELSEVIER2020

Loops in AdS: from the spectral representation to position space

Din Carmi

We compute a family of scalar loop diagrams in AdS. We use the spectral representation to derive various bulk vertex/propagator identities, and these identities enable to reduce certain loop bubble diagrams to lower loop diagrams, and often to tree- level ...

Springer Nature2020

Unique decomposition of homogeneous languages and application to isothetic regions

Nicolas René Jean Ninin

A language is said to be homogeneous when all its words have the same length. Homogeneous languages thus form a monoid under concatenation. It becomes freely commutative under the simultaneous actions of every permutation group G(n) on the collection of ho ...

2019

Role of higher order plasmonic modes in one-dimensional nanogratings

Ershad Mohammadi, Foziyeh Sohrabi

By theoretically investigating the optical behavior of one-dimensional gold nanogratings using Fourier Modal Method, we have shown that both integer and non-integer multiples of surface plasmon polariton wavelengths should be taken into consideration in sp ...

SPRINGER2019

Forbidden induced subposets of given height

Istvan Tomon

Let P be a partially ordered set. The function La* (n, P) denotes the size of the largest family F subset of 2([n]) that does not contain an induced copy of P. It was proved by Methuku and Palvolgyi that there exists a constant C-P (depending only on P) su ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Efficient Greedy Coordinate Descent for Composite Problems

Martin Jaggi, Sebastian Urban Stich, Sai Praneeth Reddy Karimireddy, Anastasiia Koloskova

Coordinate descent with random coordinate selection is the current state of the art for many large scale optimization problems. However, greedy selection of the steepest coordinate on smooth problems can yield convergence rates independent of the dimension ...

2019

The Bounded Cohomology of SL2 Over Local Fields and S-Integers

Nicolas Monod

It is proved that the continuous bounded cohomology of SL2(k) vanishes in all positive degrees whenever k is a non-Archimedean local field. This holds more generally for boundary-transitive groups of tree automorphisms and implies low degree vanishing for ...

OXFORD UNIV PRESS2019