Let $x=(x_1,x_2,\cdots,x_n)^T$ be a vector of non-zero algebraic numbers, the
set
$\mathcal{R}_x:=\{(k_1,k_2,\cdots,k_n)^T\in\mathbb{Z}^n\;|\;x_1^{k_1}x_2^{k_2}\cdots
x_n^{k_n}=1\}$ is called \emph{the multiplicative dependence lattice} of $x$.
This paper develops an efficient incremental algorithm to compute a basis of
$\mathcal{R}_x$. This algorithm constructs inductively a basis of the lattice
as the dimension increases. This is the very first algorithm for computing the
basis of the lattice, although a lot of efforts have been made to understand
this lattice. In this paper we propose the conception of the \emph{rank} of a
finite sequence of non-zero algebraic numbers, which turns out to be closely
related to the rank of the lattice, and as well as to the complexity. The
complexity of the algorithm depends not mainly on the dimension $n$ but on the
rank of the sequence $x_1,x_2,\cdots,x_n$, which can be much smaller than $n$.

more |
pdf
| html
None.

ComputerPapers:
Incrementally and inductively constructing basis of multiplicative dependence lattice of non-zero algebraic numbers. https://t.co/ykwWyHXgl6

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 8889

Unqiue Words: 1817

An additive fast Fourier transform over a finite field of characteristic two
efficiently evaluates polynomials at every element of an $\mathbb{F}_2$-linear
subspace of the field. We view these transforms as performing a change of basis
from the monomial basis to the associated Lagrange basis, and consider the
problem of performing the various conversions between these two bases, the
associated Newton basis, and the '' novel '' basis of Lin, Chung and Han (FOCS
2014). Existing algorithms are divided between two families, those designed for
arbitrary subspaces and more efficient algorithms designed for specially
constructed subspaces of fields with degree equal to a power of two. We
generalise techniques from both families to provide new conversion algorithms
that may be applied to arbitrary subspaces, but which benefit equally from the
specially constructed subspaces. We then construct subspaces of fields with
smooth degree for which our algorithms provide better performance than existing
algorithms.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 27382

Unqiue Words: 2924

Simply put, a sparse polynomial is one whose zero coefficients are not
explicitly stored. Such objects are ubiquitous in exact computing, and so
naturally we would like to have efficient algorithms to handle them. However,
with this compact storage comes new algorithmic challenges, as fast algorithms
for dense polynomials may no longer be efficient. In this tutorial we examine
the state of the art for sparse polynomial algorithms in three areas:
arithmetic, interpolation, and factorization. The aim is to highlight recent
progress both in theory and in practice, as well as opportunities for future
work.

more |
pdf
| html
None.

ComputerPapers:
What Can (and Can't) we Do with Sparse Polynomials?. https://t.co/0ym0V6FQUB

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 6676

Unqiue Words: 2184

We describe the Aligator.jl software package for automatically generating all
polynomial invariants of the rich class of extended P-solvable loops with
nested conditionals. Aligator.jl is written in the programming language Julia
and is open-source. Aligator.jl transforms program loops into a system of
algebraic recurrences and implements techniques from symbolic computation to
solve recurrences, derive closed form solutions of loop variables and infer the
ideal of polynomial invariants by variable elimination based on Gr\"obner basis
computation.

more |
pdf
| html
None.

M157q_News_RSS:
Aligator.jl - A Julia Package for Loop Invariant Generation. (arXiv:1808.05394v1 [https://t.co/LljFWnr6hA])
https://t.co/Q30DI64HsF
We describe the Aligator.j

Aligator is a Mathematica software package for generating loop invariants.

Stargazers: 0

Subscribers: 4

Subscribers: 4

Forks: 0

Open Issues: 0

Open Issues: 0

None.

Sample Sizes : None.

Authors: 3

Total Words: 2245

Unqiue Words: 941

In perturbative calculations, e.g., in the setting of Quantum Chromodynamics
(QCD) one aims at the evaluation of Feynman integrals. Here one is often faced
with the problem to simplify multiple nested integrals or sums to expressions
in terms of indefinite nested integrals or sums. Furthermore, one seeks for
solutions of coupled systems of linear differential equations, that can be
represented in terms of indefinite nested sums (or integrals). In this article
we elaborate the main tools and the corresponding packages, that we have
developed and intensively used within the last 10 years in the course of our
QCD-calculations.

more |
pdf
| html
MathPHYPapers:
Computer algebra tools for Feynman integrals and related multi-sums. https://t.co/rjdkpANStx

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 7508

Unqiue Words: 1988

This volume contains the proceedings of the Fifteenth International Workshop
on the ACL2 Theorem Prover and Its Applications (ACL2-2018), a two-day workshop
held in Austin, Texas, USA, on November 5-6, 2018, immediately after FMCAD'18.
The proceedings of ACL2-2018 include eleven long papers and two extended
abstracts.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

We look at Bohemian matrices, specifically those with entries from $\{-1, 0,
{+1}\}$. More, we specialize the matrices to be upper Hessenberg, with
subdiagonal entries $\pm1$. Many properties remain after these specializations,
some of which surprised us. We find two recursive formulae for the
characteristic polynomials of upper Hessenberg matrices. Focusing on only those
matrices whose characteristic polynomials have maximal height allows us to
explicitly identify these polynomials and give a lower bound on their height.
This bound is exponential in the order of the matrix. We count stable matrices,
normal matrices, and neutral matrices, and tabulate the results of our
experiments. We prove a theorem about the only possible kinds of normal
matrices amongst a specific family of Bohemian upper Hessenberg matrices.

more |
pdf
| html
None.

None.

Sample Sizes : None.

Authors: 6

Total Words: 7998

Unqiue Words: 2076

We present a randomized quantum algorithm for polynomial factorization over
finite fields. For polynomials of degree $n$ over a finite field $\F_q$, the
average-case complexity of our algorithm is an expected $O(n^{1 + o(1)} \log^{2
+ o(1)}q)$ bit operations. Only for a negligible subset of polynomials of
degree $n$ our algorithm has a higher complexity of $O(n^{4 / 3 + o(1)} \log^{2
+ o(1)}q)$ bit operations. This breaks the classical $3/2$-exponent barrier for
polynomial factorization over finite fields \cite{guo2016alg}.

more |
pdf
| html
None.

enclanglement:
A quantum algorithm for factoring polynomials
(for some reason, not posted under quant-ph).
https://t.co/pxMFlBJzux

MathPaper:
Toward an Optimal Quantum Algorithm for Polynomial Factorization over Finite Fields. https://t.co/DoCDEdMpj9

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 6430

Unqiue Words: 1451

We develop a probabilistic algorithm for computing elimination ideals of
likelihood equations, which is for larger models by far more efficient than
directly computing Groebner bases or the interpolation method proposed in the
first author's previous work. The efficiency is improved by a theoretical
result showing that the sum of data variables appears in most coefficients of
the generator polynomial of elimination ideal. Furthermore, applying the known
structures of Newton polytopes of discriminants, we can also efficiently deduce
discriminants of the elimination ideals. For instance, the discriminants of 3
by 3 matrix model and one Jukes-Cantor model in phylogenetics (with sizes over
30 GB and 8 GB text files, respectively) can be computed by our methods.

more |
pdf
| html
None.

StatsPapers:
Computing Elimination Ideals and Discriminants of Likelihood Equations. https://t.co/4dC06cDFOa

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 17165

Unqiue Words: 3179

The article addresses the problem whether indefinite double sums involving a
generic sequence can be simplified in terms of indefinite single sums.
Depending on the structure of the double sum, the proposed summation machinery
may provide such a simplification without exceptions. If it fails, it may
suggest a more advanced simplification introducing in addition a single nested
sum where the summand has to satisfy a particular constraint. More precisely,
an explicitly given parameterized telescoping equation must hold. Restricting
to the case that the arising unspecified sequences are specialized to the class
of indefinite nested sums defined over hypergeometric, multi-basic or mixed
hypergeometric products, it can be shown that this constraint is not only
sufficient but also necessary.

more |
pdf
| html
None.

MathPaper:
Towards a symbolic summation theory for unspecified sequences. https://t.co/UwwFmJn0JY

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 16226

Unqiue Words: 2796

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 57,756 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible