-
Fast interpolation of sparse multivariate polynomials
Authors:
Joris van der Hoeven,
Grégoire Lecerf
Abstract:
Consider a sparse multivariate polynomial f with integer coefficients. Assume that f is represented as a "modular black box polynomial", e.g. via an algorithm to evaluate f at arbitrary integer points, modulo arbitrary positive integers. The problem of sparse interpolation is to recover f in its usual sparse representation, as a sum of coefficients times monomials. For the first time we present a…
▽ More
Consider a sparse multivariate polynomial f with integer coefficients. Assume that f is represented as a "modular black box polynomial", e.g. via an algorithm to evaluate f at arbitrary integer points, modulo arbitrary positive integers. The problem of sparse interpolation is to recover f in its usual sparse representation, as a sum of coefficients times monomials. For the first time we present a quasi-optimal algorithm for this task.
△ Less
Submitted 29 December, 2023;
originally announced December 2023.
-
Factoring sparse polynomials fast
Authors:
Alexander Demin,
Joris van der Hoeven
Abstract:
Consider a sparse polynomial in several variables given explicitly as a sum of non-zero terms with coefficients in an effective field. In this paper, we present several algorithms for factoring such polynomials and related tasks (such as gcd computation, square-free factorization, content-free factorization, and root extraction). Our methods are all based on sparse interpolation, but follow two ma…
▽ More
Consider a sparse polynomial in several variables given explicitly as a sum of non-zero terms with coefficients in an effective field. In this paper, we present several algorithms for factoring such polynomials and related tasks (such as gcd computation, square-free factorization, content-free factorization, and root extraction). Our methods are all based on sparse interpolation, but follow two main lines of attack: iteration on the number of variables and more direct reductions to the univariate or bivariate case. We present detailed probabilistic complexity bounds in terms of the complexity of sparse interpolation and evaluation.
△ Less
Submitted 28 December, 2023;
originally announced December 2023.
-
Optimizing the half-gcd algorithm
Authors:
Joris van der Hoeven
Abstract:
In this paper, we propose a carefully optimized "half-gcd" algorithm for polynomials. We achieve a constant speed-up with respect to previous work for the asymptotic time complexity. We also discuss special optimizations that are possible when polynomial multiplication is done using radix two FFTs.
In this paper, we propose a carefully optimized "half-gcd" algorithm for polynomials. We achieve a constant speed-up with respect to previous work for the asymptotic time complexity. We also discuss special optimizations that are possible when polynomial multiplication is done using radix two FFTs.
△ Less
Submitted 23 December, 2022;
originally announced December 2022.
-
Forecasting Graph Signals with Recursive MIMO Graph Filters
Authors:
Jelmer van der Hoeven,
Alberto Natali,
Geert Leus
Abstract:
Forecasting time series on graphs is a fundamental problem in graph signal processing. When each entity of the network carries a vector of values for each time stamp instead of a scalar one, existing approaches resort to the use of product graphs to combine this multidimensional information, at the expense of creating a larger graph. In this paper, we show the limitations of such approaches, and p…
▽ More
Forecasting time series on graphs is a fundamental problem in graph signal processing. When each entity of the network carries a vector of values for each time stamp instead of a scalar one, existing approaches resort to the use of product graphs to combine this multidimensional information, at the expense of creating a larger graph. In this paper, we show the limitations of such approaches, and propose extensions to tackle them. Then, we propose a recursive multiple-input multiple-output graph filter which encompasses many already existing models in the literature while being more flexible. Numerical simulations on a real world data set show the effectiveness of the proposed models.
△ Less
Submitted 27 October, 2022;
originally announced October 2022.
-
Meaningful human control: actionable properties for AI system development
Authors:
Luciano Cavalcante Siebert,
Maria Luce Lupetti,
Evgeni Aizenberg,
Niek Beckers,
Arkady Zgonnikov,
Herman Veluwenkamp,
David Abbink,
Elisa Giaccardi,
Geert-Jan Houben,
Catholijn M. Jonker,
Jeroen van den Hoven,
Deborah Forster,
Reginald L. Lagendijk
Abstract:
How can humans remain in control of artificial intelligence (AI)-based systems designed to perform tasks autonomously? Such systems are increasingly ubiquitous, creating benefits - but also undesirable situations where moral responsibility for their actions cannot be properly attributed to any particular person or group. The concept of meaningful human control has been proposed to address responsi…
▽ More
How can humans remain in control of artificial intelligence (AI)-based systems designed to perform tasks autonomously? Such systems are increasingly ubiquitous, creating benefits - but also undesirable situations where moral responsibility for their actions cannot be properly attributed to any particular person or group. The concept of meaningful human control has been proposed to address responsibility gaps and mitigate them by establishing conditions that enable a proper attribution of responsibility for humans; however, clear requirements for researchers, designers, and engineers are yet inexistent, making the development of AI-based systems that remain under meaningful human control challenging. In this paper, we address the gap between philosophical theory and engineering practice by identifying, through an iterative process of abductive thinking, four actionable properties for AI-based systems under meaningful human control, which we discuss making use of two applications scenarios: automated vehicles and AI-based hiring. First, a system in which humans and AI algorithms interact should have an explicitly defined domain of morally loaded situations within which the system ought to operate. Second, humans and AI agents within the system should have appropriate and mutually compatible representations. Third, responsibility attributed to a human should be commensurate with that human's ability and authority to control the system. Fourth, there should be explicit links between the actions of the AI agents and actions of humans who are aware of their moral responsibility. We argue that these four properties will support practically-minded professionals to take concrete steps toward designing and engineering for AI systems that facilitate meaningful human control.
△ Less
Submitted 19 May, 2022; v1 submitted 25 November, 2021;
originally announced December 2021.
-
Designing for Human Rights in AI
Authors:
Evgeni Aizenberg,
Jeroen van den Hoven
Abstract:
In the age of big data, companies and governments are increasingly using algorithms to inform hiring decisions, employee management, policing, credit scoring, insurance pricing, and many more aspects of our lives. AI systems can help us make evidence-driven, efficient decisions, but can also confront us with unjustified, discriminatory decisions wrongly assumed to be accurate because they are made…
▽ More
In the age of big data, companies and governments are increasingly using algorithms to inform hiring decisions, employee management, policing, credit scoring, insurance pricing, and many more aspects of our lives. AI systems can help us make evidence-driven, efficient decisions, but can also confront us with unjustified, discriminatory decisions wrongly assumed to be accurate because they are made automatically and quantitatively. It is becoming evident that these technological developments are consequential to people's fundamental human rights. Despite increasing attention to these urgent challenges in recent years, technical solutions to these complex socio-ethical problems are often developed without empirical study of societal context and the critical input of societal stakeholders who are impacted by the technology. On the other hand, calls for more ethically- and socially-aware AI often fail to provide answers for how to proceed beyond stressing the importance of transparency, explainability, and fairness. Bridging these socio-technical gaps and the deep divide between abstract value language and design requirements is essential to facilitate nuanced, context-dependent design choices that will support moral and social values. In this paper, we bridge this divide through the framework of Design for Values, drawing on methodologies of Value Sensitive Design and Participatory Design to present a roadmap for proactively engaging societal stakeholders to translate fundamental human rights into context-dependent design requirements through a structured, inclusive, and transparent process.
△ Less
Submitted 6 July, 2020; v1 submitted 11 May, 2020;
originally announced May 2020.
-
Give more data, awareness and control to individual citizens, and they will help COVID-19 containment
Authors:
Mirco Nanni,
Gennady Andrienko,
Albert-László Barabási,
Chiara Boldrini,
Francesco Bonchi,
Ciro Cattuto,
Francesca Chiaromonte,
Giovanni Comandé,
Marco Conti,
Mark Coté,
Frank Dignum,
Virginia Dignum,
Josep Domingo-Ferrer,
Paolo Ferragina,
Fosca Giannotti,
Riccardo Guidotti,
Dirk Helbing,
Kimmo Kaski,
Janos Kertesz,
Sune Lehmann,
Bruno Lepri,
Paul Lukowicz,
Stan Matwin,
David Megías Jiménez,
Anna Monreale
, et al. (14 additional authors not shown)
Abstract:
The rapid dynamics of COVID-19 calls for quick and effective tracking of virus transmission chains and early detection of outbreaks, especially in the phase 2 of the pandemic, when lockdown and other restriction measures are progressively withdrawn, in order to avoid or minimize contagion resurgence. For this purpose, contact-tracing apps are being proposed for large scale adoption by many countri…
▽ More
The rapid dynamics of COVID-19 calls for quick and effective tracking of virus transmission chains and early detection of outbreaks, especially in the phase 2 of the pandemic, when lockdown and other restriction measures are progressively withdrawn, in order to avoid or minimize contagion resurgence. For this purpose, contact-tracing apps are being proposed for large scale adoption by many countries. A centralized approach, where data sensed by the app are all sent to a nation-wide server, raises concerns about citizens' privacy and needlessly strong digital surveillance, thus alerting us to the need to minimize personal data collection and avoiding location tracking. We advocate the conceptual advantage of a decentralized approach, where both contact and location data are collected exclusively in individual citizens' "personal data stores", to be shared separately and selectively, voluntarily, only when the citizen has tested positive for COVID-19, and with a privacy preserving level of granularity. This approach better protects the personal sphere of citizens and affords multiple benefits: it allows for detailed information gathering for infected people in a privacy-preserving fashion; and, in turn this enables both contact tracing, and, the early detection of outbreak hotspots on more finely-granulated geographic scale. Our recommendation is two-fold. First to extend existing decentralized architectures with a light touch, in order to manage the collection of location data locally on the device, and allow the user to share spatio-temporal aggregates - if and when they want, for specific aims - with health authorities, for instance. Second, we favour a longer-term pursuit of realizing a Personal Data Store vision, giving users the opportunity to contribute to collective good in the measure they want, enhancing self-awareness, and cultivating collective efforts for rebuilding society.
△ Less
Submitted 16 April, 2020; v1 submitted 10 April, 2020;
originally announced April 2020.
-
Improving Confidence in the Estimation of Values and Norms
Authors:
Luciano Cavalcante Siebert,
Rijk Mercuur,
Virginia Dignum,
Jeroen van den Hoven,
Catholijn Jonker
Abstract:
Autonomous agents (AA) will increasingly be interacting with us in our daily lives. While we want the benefits attached to AAs, it is essential that their behavior is aligned with our values and norms. Hence, an AA will need to estimate the values and norms of the humans it interacts with, which is not a straightforward task when solely observing an agent's behavior. This paper analyses to what ex…
▽ More
Autonomous agents (AA) will increasingly be interacting with us in our daily lives. While we want the benefits attached to AAs, it is essential that their behavior is aligned with our values and norms. Hence, an AA will need to estimate the values and norms of the humans it interacts with, which is not a straightforward task when solely observing an agent's behavior. This paper analyses to what extent an AA is able to estimate the values and norms of a simulated human agent (SHA) based on its actions in the ultimatum game. We present two methods to reduce ambiguity in profiling the SHAs: one based on search space exploration and another based on counterfactual analysis. We found that both methods are able to increase the confidence in estimating human values and norms, but differ in their applicability, the latter being more efficient when the number of interactions with the agent is to be minimized. These insights are useful to improve the alignment of AAs with human values and norms.
△ Less
Submitted 2 April, 2020;
originally announced April 2020.
-
LU factorization with errors *
Authors:
Jean-Guillaume Dumas,
Joris Van Der Hoeven,
Clément Pernet,
Daniel Roche
Abstract:
We present new algorithms to detect and correct errors in the lower-upper factorization of a matrix, or the triangular linear system solution, over an arbitrary field. Our main algorithms do not require any additional information or encoding other than the original inputs and the erroneous output. Their running time is softly linear in the dimension times the number of errors when there are few er…
▽ More
We present new algorithms to detect and correct errors in the lower-upper factorization of a matrix, or the triangular linear system solution, over an arbitrary field. Our main algorithms do not require any additional information or encoding other than the original inputs and the erroneous output. Their running time is softly linear in the dimension times the number of errors when there are few errors, smoothly growing to the cost of fast matrix multiplication as the number of errors increases. We also present applications to general linear system solving.
△ Less
Submitted 30 January, 2019;
originally announced January 2019.
-
Epithelium segmentation using deep learning in H&E-stained prostate specimens with immunohistochemistry as reference standard
Authors:
Wouter Bulten,
Péter Bándi,
Jeffrey Hoven,
Rob van de Loo,
Johannes Lotz,
Nick Weiss,
Jeroen van der Laak,
Bram van Ginneken,
Christina Hulsbergen-van de Kaa,
Geert Litjens
Abstract:
Prostate cancer (PCa) is graded by pathologists by examining the architectural pattern of cancerous epithelial tissue on hematoxylin and eosin (H&E) stained slides. Given the importance of gland morphology, automatically differentiating between glandular epithelial tissue and other tissues is an important prerequisite for the development of automated methods for detecting PCa. We propose a new met…
▽ More
Prostate cancer (PCa) is graded by pathologists by examining the architectural pattern of cancerous epithelial tissue on hematoxylin and eosin (H&E) stained slides. Given the importance of gland morphology, automatically differentiating between glandular epithelial tissue and other tissues is an important prerequisite for the development of automated methods for detecting PCa. We propose a new method, using deep learning, for automatically segmenting epithelial tissue in digitized prostatectomy slides. We employed immunohistochemistry (IHC) to render the ground truth less subjective and more precise compared to manual outlining on H&E slides, especially in areas with high-grade and poorly differentiated PCa. Our dataset consisted of 102 tissue blocks, including both low and high grade PCa. From each block a single new section was cut, stained with H&E, scanned, restained using P63 and CK8/18 to highlight the epithelial structure, and scanned again. The H&E slides were co-registered to the IHC slides. On a subset of the IHC slides we applied color deconvolution, corrected stain errors manually, and trained a U-Net to perform segmentation of epithelial structures. Whole-slide segmentation masks generated by the IHC U-Net were used to train a second U-Net on H&E. Our system makes precise cell-level segmentations and segments both intact glands as well as individual (tumor) epithelial cells. We achieved an F1-score of 0.895 on a hold-out test set and 0.827 on an external reference set from a different center. We envision this segmentation as being the first part of a fully automated prostate cancer detection and grading pipeline.
△ Less
Submitted 8 February, 2019; v1 submitted 17 August, 2018;
originally announced August 2018.
-
Faster integer multiplication using short lattice vectors
Authors:
David Harvey,
Joris van der Hoeven
Abstract:
We prove that $n$-bit integers may be multiplied in $O(n \log n \, 4^{\log^* n})$ bit operations. This complexity bound had been achieved previously by several authors, assuming various unproved number-theoretic hypotheses. Our proof is unconditional, and depends in an essential way on Minkowski's theorem concerning lattice vectors in symmetric convex sets.
We prove that $n$-bit integers may be multiplied in $O(n \log n \, 4^{\log^* n})$ bit operations. This complexity bound had been achieved previously by several authors, assuming various unproved number-theoretic hypotheses. Our proof is unconditional, and depends in an essential way on Minkowski's theorem concerning lattice vectors in symmetric convex sets.
△ Less
Submitted 22 February, 2018;
originally announced February 2018.
-
Faster integer and polynomial multiplication using cyclotomic coefficient rings
Authors:
David Harvey,
Joris van der Hoeven
Abstract:
We present an algorithm that computes the product of two n-bit integers in O(n log n (4\sqrt 2)^{log^* n}) bit operations. Previously, the best known bound was O(n log n 6^{log^* n}). We also prove that for a fixed prime p, polynomials in F_p[X] of degree n may be multiplied in O(n log n 4^{log^* n}) bit operations; the previous best bound was O(n log n 8^{log^* n}).
We present an algorithm that computes the product of two n-bit integers in O(n log n (4\sqrt 2)^{log^* n}) bit operations. Previously, the best known bound was O(n log n 6^{log^* n}). We also prove that for a fixed prime p, polynomials in F_p[X] of degree n may be multiplied in O(n log n 4^{log^* n}) bit operations; the previous best bound was O(n log n 8^{log^* n}).
△ Less
Submitted 11 December, 2017;
originally announced December 2017.
-
Faster integer multiplication using plain vanilla FFT primes
Authors:
David Harvey,
Joris van der Hoeven
Abstract:
Assuming a conjectural upper bound for the least prime in an arithmetic progression, we show that n-bit integers may be multiplied in O(n log n 4^(log^* n)) bit operations.
Assuming a conjectural upper bound for the least prime in an arithmetic progression, we show that n-bit integers may be multiplied in O(n log n 4^(log^* n)) bit operations.
△ Less
Submitted 16 October, 2017; v1 submitted 21 November, 2016;
originally announced November 2016.
-
Modular SIMD arithmetic in Mathemagix
Authors:
Joris van der Hoeven,
Grégoire Lecerf,
Guillaume Quintin
Abstract:
Modular integer arithmetic occurs in many algorithms for computer algebra, cryptography, and error correcting codes. Although recent microprocessors typically offer a wide range of highly optimized arithmetic functions, modular integer operations still require dedicated implementations. In this article, we survey existing algorithms for modular integer arithmetic, and present detailed vectorized c…
▽ More
Modular integer arithmetic occurs in many algorithms for computer algebra, cryptography, and error correcting codes. Although recent microprocessors typically offer a wide range of highly optimized arithmetic functions, modular integer operations still require dedicated implementations. In this article, we survey existing algorithms for modular integer arithmetic, and present detailed vectorized counterparts. We also present several applications, such as fast modular Fourier transforms and multiplication of integer polynomials and matrices. The vectorized algorithms have been implemented in C++ inside the free computer algebra and analysis system Mathemagix. The performance of our implementation is illustrated by various benchmarks.
△ Less
Submitted 12 July, 2014;
originally announced July 2014.
-
Faster polynomial multiplication over finite fields
Authors:
David Harvey,
Joris van der Hoeven,
Grégoire Lecerf
Abstract:
Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n) = O(n log n 8^(log^* n) log p), where log^* is the iterated logarithm. This is the first known Fürer-type complexity bound for F_p[X], and improves on the previously best known bound M_p(n) = O(n log n log log n log p).
Let p be a prime, and let M_p(n) denote the bit complexity of multiplying two polynomials in F_p[X] of degree less than n. For n large compared to p, we establish the bound M_p(n) = O(n log n 8^(log^* n) log p), where log^* is the iterated logarithm. This is the first known Fürer-type complexity bound for F_p[X], and improves on the previously best known bound M_p(n) = O(n log n log log n log p).
△ Less
Submitted 12 July, 2014;
originally announced July 2014.
-
Even faster integer multiplication
Authors:
David Harvey,
Joris van der Hoeven,
Grégoire Lecerf
Abstract:
We give a new proof of Fürer's bound for the cost of multiplying n-bit integers in the bit complexity model. Unlike Fürer, our method does not require constructing special coefficient rings with "fast" roots of unity. Moreover, we prove the more explicit bound O(n log n K^(log^* n))$ with K = 8. We show that an optimised variant of Fürer's algorithm achieves only K = 16, suggesting that the new al…
▽ More
We give a new proof of Fürer's bound for the cost of multiplying n-bit integers in the bit complexity model. Unlike Fürer, our method does not require constructing special coefficient rings with "fast" roots of unity. Moreover, we prove the more explicit bound O(n log n K^(log^* n))$ with K = 8. We show that an optimised variant of Fürer's algorithm achieves only K = 16, suggesting that the new algorithm is faster than Fürer's by a factor of 2^(log^* n). Assuming standard conjectures about the distribution of Mersenne primes, we give yet another algorithm that achieves K = 4.
△ Less
Submitted 12 July, 2014;
originally announced July 2014.
-
FuturICT - The Road towards Ethical ICT
Authors:
Jeroen van den Hoven,
Dirk Helbing,
Dino Pedreschi,
Josep Domingo-Ferrer,
Fosca Gianotti,
Markus Christen
Abstract:
The pervasive use of information and communication technology (ICT) in modern societies enables countless opportunities for individuals, institutions, businesses and scientists, but also raises difficult ethical and social problems. In particular, ICT helped to make societies more complex and thus harder to understand, which impedes social and political interventions to avoid harm and to increase…
▽ More
The pervasive use of information and communication technology (ICT) in modern societies enables countless opportunities for individuals, institutions, businesses and scientists, but also raises difficult ethical and social problems. In particular, ICT helped to make societies more complex and thus harder to understand, which impedes social and political interventions to avoid harm and to increase the common good. To overcome this obstacle, the large-scale EU flagship proposal FuturICT intends to create a platform for accessing global human knowledge as a public good and instruments to increase our understanding of the information society by making use of ICT-based research. In this contribution, we outline the ethical justification for such an endeavor. We argue that the ethical issues raised by FuturICT research projects overlap substantially with many of the known ethical problems emerging from ICT use in general. By referring to the notion of Value Sensitive Design, we show for the example of privacy how this core value of responsible ICT can be protected in pursuing research in the framework of FuturICT. In addition, we discuss further ethical issues and outline the institutional design of FuturICT allowing to address them.
△ Less
Submitted 30 October, 2012;
originally announced October 2012.
-
Quasi-optimal multiplication of linear differential operators
Authors:
Alexandre Benoit,
Alin Bostan,
Joris van der Hoeven
Abstract:
We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.
We show that linear differential operators with polynomial coefficients over a field of characteristic zero can be multiplied in quasi-optimal time. This answers an open question raised by van der Hoeven.
△ Less
Submitted 17 August, 2012;
originally announced August 2012.
-
On the bit-complexity of sparse polynomial multiplication
Authors:
Joris van der Hoeven,
Grégoire Lecerf
Abstract:
In this paper, we present fast algorithms for the product of two multivariate polynomials in sparse representation. The bit complexity of our algorithms are studied in detail for various types of coefficients, and we derive new complexity results for the power series multiplication in many variables. Our algorithms are implemented and freely available within the Mathemagix software. We show that…
▽ More
In this paper, we present fast algorithms for the product of two multivariate polynomials in sparse representation. The bit complexity of our algorithms are studied in detail for various types of coefficients, and we derive new complexity results for the power series multiplication in many variables. Our algorithms are implemented and freely available within the Mathemagix software. We show that their theoretical costs are well-reflected in practice.
△ Less
Submitted 26 January, 2009;
originally announced January 2009.
-
Homotopy methods for multiplication modulo triangular sets
Authors:
Alin Bostan,
Muhammad Chowdhury,
Joris van der Hoeven,
Eric Schost
Abstract:
We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li, Moreno Maza and Schost, we propose an algorithm that relies on homotopy and fast evaluation-interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given to notably addition of al…
▽ More
We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li, Moreno Maza and Schost, we propose an algorithm that relies on homotopy and fast evaluation-interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given to notably addition of algebraic numbers in small characteristic.
△ Less
Submitted 23 January, 2009;
originally announced January 2009.
