14 citations · 53 across the 17 of their papers we have counts for
18 papers
Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms
Alperen A. Ergür, Josué Tonelli-Cueto, Elias Tsigaridas
We introduce beyond-worst-case analysis into symbolic computation. This is an extensive field which almost entirely relies on worst-case bit complexity, and we start from a basic p…
Is uniform expressivity too restrictive? Towards efficient expressivity of graph neural networks
Sammy Khalife, Josué Tonelli-Cueto
Uniform expressivity guarantees that a Graph Neural Network (GNN) can express a query without the parameters depending on the size of the input graphs. This property is desirable i…
Almost Orthogonal Arrays: Search Three Ways
Luis Martínez, María Merino, Juan Manuel Montoya +1
Orthogonal arrays play a fundamental role in many applications. However, constructing orthogonal arrays with the required parameters for an application usually is extremely difficu…
Tensor learning with orthogonal, Lorentz, and symplectic symmetries
Wilson G. Gregory, Josué Tonelli-Cueto, Nicholas F. Marshall +2
Tensors are a fundamental data structure for many scientific contexts, such as time series analysis, materials science, and physics, among many others. Improving our ability to pro…
Some Lower Bounds on the Reach of an Algebraic Variety
Chris La Valle, Josué Tonelli-Cueto
Separation bounds are a fundamental measure of the complexity of solving a zero-dimensional system as it measures how difficult it is to separate its zeroes. In the positive dimens…
On the Number of Real Zeros of Random Sparse Polynomial Systems
Alperen A. Ergür, Máté L. Telek, Josué Tonelli-Cueto
Consider a random system of random real polynomials in variables, where each has a prescribed set of expon…
Ultrametric Smale's -theory
Jazz G. Suchen, Josué Tonelli-Cueto
We present a version of Smale's -theory for ultrametric fields, such as the -adics and their extensions, which gives us a multivariate version of Hensel's lemma.
A -adic Descartes solver: the Strassman solver
Josué Tonelli-Cueto
Solving polynomials is a fundamental computational problem in mathematics. In the real setting, we can use Descartes' rule of signs to efficiently isolate the real roots of a squar…
On the Error of Random Sampling: Uniformly Distributed Random Points on Parametric Curves
Apostolos Chalkis, Christina Katsamaki, Josué Tonelli-Cueto
Given a parametric polynomial curve , how can we sample a random point in such a way that it is distributed unifor…
Beyond Worst-Case Analysis for Root Isolation Algorithms
Alperen A. Ergür, Josué Tonelli-Cueto, Elias Tsigaridas
Isolating the real roots of univariate polynomials is a fundamental problem in symbolic computation and it is arguably one of the most important problems in computational mathemati…
Probabilistic bounds on best rank-one approximation ratio
Khazhgali Kozhasov, Josué Tonelli-Cueto
We provide new upper and lower bounds on the minimum possible ratio of the spectral and Frobenius norms of a (partially) symmetric tensor. In the particular case of general tensors…
Functional norms, condition numbers and numerical algorithms in algebraic geometry
Felipe Cucker, Alperen A. Ergür, Josué Tonelli-Cueto
In numerical linear algebra, a well-established practice is to choose a norm that exploits the structure of the problem at hand in order to optimize accuracy or computational compl…
Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces
Josué Tonelli-Cueto, Elias Tsigaridas
The condition-based complexity analysis framework is one of the gems of modern numerical algebraic geometry and theoretical computer science. Among the challenges that it poses is…
On the Complexity of the Plantinga-Vegter Algorithm
Felipe Cucker, Alperen A. Ergür, Josué Tonelli-Cueto
We introduce tools from numerical analysis and high dimensional probability for precision control and complexity analysis of subdivision-based algorithms in computational geometry.…
Computing the Homology of Semialgebraic Sets. II: General formulas
Peter Bürgisser, Felipe Cucker, Josué Tonelli-Cueto
We describe and analyze a numerical algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. The algorithm wor…
Plantinga-Vegter algorithm takes average polynomial time
Felipe Cucker, Alperen A. Ergür, Josue Tonelli-Cueto
We exhibit a condition-based analysis of the adaptive subdivision algorithm due to Plantinga and Vegter. The first complexity analysis of the PV Algorithm is due to Burr, Gao and T…
On the Number of Real Zeros of Random Fewnomials
Peter Bürgisser, Alperen A. Ergür, Josué Tonelli-Cueto
Consider a system of random real polynomials in variables, where each has a prescribed set of terms described by a set $A\subseteq \mathbb{…
Computing the Homology of Semialgebraic Sets I: Lax Formulas
Peter Bürgisser, Felipe Cucker, Josué Tonelli-Cueto
We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of closed semialgebraic sets given by Boolean formulas without negations ov…