Publications related to Efficient multiplication using type $2$ optimal normal bases

Finite free convolutions of polynomials

We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric addi ...

SPRINGER HEIDELBERG2022

Harmonic decomposition of the trace of 1D transfer matrices in layered media

Antonio Joaquin Garcia Suarez

The Transfer Matrix formalism is ubiquitous when it comes to study wave propagation in various stratified media, applications ranging from Seismology to Quantum Mechanics. A relation between variables at two points in two different layers can be establishe ...

2022

A Determinantal Identity for the Permanent of a Rank 2 Matrix

Adam Wade Marcus

We prove an identity relating the permanent of a rank 2 matrix and the determinants of its Hadamard powers. When viewed in the right way, the resulting formula looks strikingly similar to an identity of Carlitz and Levine, suggesting the possibility that t ...

TAYLOR & FRANCIS INC2022

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Interlacing families III: Sharper restricted invertibility estimates

Adam Wade Marcus

We use the method of interlacing families of polynomials to derive a simple proof of Bourgain and Tzafriri's Restricted Invertibility Principle, and then to sharpen the result in two ways. We show that the stable rank can be replaced by the Schatten 4-norm ...

HEBREW UNIV MAGNES PRESS2021

Computation of Al-Salam Carlitz and Askey-Wilson moments using Motzkin paths

Gaspard Ohlmann

In this paper we study the moments of polynomials from the Askey scheme, and we focus on Askey-Wilson polynomials. More precisely, we give a combinatorial proof for the case where d = 0. Their values have already been computed by Kim and Stanton in 2015, h ...

ELECTRONIC JOURNAL OF COMBINATORICS2021

A fast spectral divide-and-conquer method for banded matrices

Daniel Kressner, Ana Susnjara

Based on the spectral divide-and-conquer algorithm by Nakatsukasa and Higham [SIAM J. Sci. Comput., 35(3):A1325-A1349, 2013], we propose a new algorithm for computing all the eigenvalues and eigenvectors of a symmetric banded matrix with small bandwidth, w ...

WILEY2021

Optimal radial basis for density-based atomic representations

Michele Ceriotti, Sergey Pozdnyakov, Jigyasa Nigam, Félix Benedito Clément Musil, Alexander Jan Goscinski

The input of almost every machine learning algorithm targeting the properties of matter at the atomic scale involves a transformation of the list of Cartesian atomic coordinates into a more symmetric representation. Many of the most popular representations ...

AIP Publishing2021

Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)

Rachid Guerraoui, Sadegh Farhadkhani, El Mahdi El Mhamdi, Le Nguyen Hoang, Sébastien Louis Alexandre Rouault, Arsany Hany Abdelmessih Guirguis

We study Byzantine collaborative learning, where n nodes seek to collectively learn from each others' local data. The data distribution may vary from one node to another. No node is trusted, and f < n nodes can behave arbitrarily. We prove that collaborati ...

2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Efficient multiplication using type $2$ optimal normal bases

Graph Chatbot

Chat with Graph Search

Finite free convolutions of polynomials

Harmonic decomposition of the trace of 1D transfer matrices in layered media

A Determinantal Identity for the Permanent of a Rank 2 Matrix

A PCP Theorem for Interactive Proofs and Applications

Interlacing families III: Sharper restricted invertibility estimates

Computation of Al-Salam Carlitz and Askey-Wilson moments using Motzkin paths

A fast spectral divide-and-conquer method for banded matrices

Optimal radial basis for density-based atomic representations

Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)

New Results in Integer and Lattice Programming

A Determinantal Identity for the Permanent of a Rank 2 Matrix

A PCP Theorem for Interactive Proofs and Applications

Finite free convolutions of polynomials

Interlacing families III: Sharper restricted invertibility estimates

Harmonic decomposition of the trace of 1D transfer matrices in layered media

New Results in Integer and Lattice Programming

Optimal radial basis for density-based atomic representations

A fast spectral divide-and-conquer method for banded matrices

Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)

Computation of Al-Salam Carlitz and Askey-Wilson moments using Motzkin paths