Publications related to Primitive recursive function

Computation Of A 30750-Bit Binary Field Discrete Logarithm

Arjen Lenstra, Robert Granger, Thorsten Kleinjung, Benjamin Pierre Charles Wesolowski

This paper reports on the computation of a discrete logarithm in the finite field F-230750, breaking by a large margin the previous record, which was set in January 2014 by a computation in F-29234. The present computation made essential use of the elimina ...

AMER MATHEMATICAL SOC2021

Multi-memristive synaptic architectures for training neural networks

Irem Boybat Kara

Highly data-centric AI workloads require that new computing paradigms be adopted because the performance of traditional CPU- and GPU-based systems are limited by data access and transfer. Training deep neural networks with millions of tunable parameters ta ...

EPFL2020

A finite element framework based on bivariate simplex splines on triangle configurations

Xiaodong Wei, Juan Cao

Recently, triangle configuration based bivariate simplex splines (referred to as TCB-spline) have been introduced to the geometric computing community. TCB-splines retain many attractive theoretic properties of classical B-splines, such as partition of uni ...

ELSEVIER SCIENCE SA2019

Permutation-based Decoding of Reed-Muller Codes in Binary Erasure Channel

Rüdiger Urbanke, Kirill Ivanov

In this paper, we consider the problem of decoding Reed-Muller (RM) codes in binary erasure channel. We propose a novel algorithm, which exploits several techniques, such as list recursive (successive cancellation) decoding based on Plotkin decomposition, ...

IEEE2019

Algorithmic Resource Verification

Ravichandhran Kandhadai Madhavan

Static estimation of resource utilisation of programs is a challenging and important problem with numerous applications. In this thesis, I present new algorithms that enable users to specify and verify their desired bounds on resource usage of functional p ...

EPFL2017

Proactive Synthesis of Recursive Tree-to-String Functions from Examples

Viktor Kuncak, Mikaël Mayer, Jad Hamza

Synthesis from examples enables non-expert users to generate programs by specifying examples of their behavior. A domain-specific form of such synthesis has been recently deployed in a widely used spreadsheet software product. In this paper we contribute t ...

2017

Improving Circuit Mapping Performance Through MIG-based Synthesis for Carry Chains

Giovanni De Micheli, Paolo Ienne, Mathias Soeken, Grace Zgheib, Xifan Tang, Pierre-Emmanuel Julien Marc Gaillardon, Ana Petkovska, Luca Gaetano Amarù, Zhufei Chu

Hard-wired carry chains in FPGAs are designed to improve efficiency of important arithmetic primitives. Although they are proven to be effective for arithmetic-rich functions, there are very few studies on the optimization opportunities of carry chains for ...

ACM2017

Deductive Synthesis and Repair

Etienne Kneuss

In this thesis, we explore techniques for the development of recursive functional programs over unbounded domains that are proved correct according to their high-level specifications. We present algorithms for automatically synthesizing executable code, st ...

EPFL2016

Undecidability through Fourier series

In computability theory a variety of combinatorial systems are encountered (word problems, production systems) that exhibit undecidability properties. Here we seek such structures in the realm of Analysis, more specifically in the area of Fourier Analysis. ...

Elsevier Science Bv2016

Tensor train approximation of moment equations for elliptic equations with lognormal coefficient

Fabio Nobile, Daniel Kressner, Francesca Bonizzoni

We study an elliptic equation with stochastic coefficient modeled as a lognormal random field. A perturbation approach is adopted, expanding the solution in Taylor series around the nominal value of the coefficient. The resulting recursive deterministic pr ...

Elsevier2016

On the use of ANOVA expansions in reduced basis methods for high-dimensional parametric partial differential equations

Jan Sickmann Hesthaven

We propose two different improvements of reduced basis (RB) methods to enable the efficient and accurate evaluation of an output functional based on the numerical solution of parametrized partial differential equations with a possibly high-dimensional para ...

Springer Verlag2016

Developing Verified Software Using Leon

Viktor Kuncak

We present Leon, a system for developing functional Scala programs annotated with contracts. Contracts in Leon can themselves refer to recursively defined functions. Leon aims to find counterexamples when functions do not meet the specifications, and proof ...

Springer-Verlag Berlin2015

Deductive Program Repair, Computer Aided Verification

Viktor Kuncak, Etienne Kneuss

We present an approach to program repair and its application to programs with recursive functions over unbounded data types. Our approach formulates program repair in the framework of deductive synthesis that uses existing program structure as a hint to gu ...

2015

Explicit Recursive and Adaptive Filtering in Reproducing Kernel Hilbert Spaces

Devis Tuia

This brief presents a methodology to develop recursive filters in reproducing kernel Hilbert spaces. Unlike previous approaches that exploit the kernel trick on filtered and then mapped samples, we explicitly define the model recursivity in the Hilbert spa ...

Ieee-Inst Electrical Electronics Engineers Inc2014

Verifying and Synthesizing Software with Recursive Functions

Viktor Kuncak

Our goal is to help people construct software that does what they wish. We develop tools and algorithms that span static and dynamic verification, constraint solving, and program synthesis. I will outline the current state our verification and synthesis sy ...

Springer-Verlag Berlin2014

An overview of the Leon verification system: verification by translation to recursive functions

Viktor Kuncak, Etienne Kneuss, Philippe Paul Henri Suter, Régis William Blanc

We present the Leon verification system for a subset of the Scala programming language. Along with several functional features of Scala, Leon supports imperative constructs such as mutations and loops, using a translation into recursive functional form. Bo ...

2013

Synthesis Modulo Recursive Functions

Viktor Kuncak, Etienne Kneuss, Philippe Paul Henri Suter, Ivan Kuraj

We describe techniques for synthesis and verification of recursive functional programs over unbounded domains. Our techniques build on top of an algorithm for satisfiability modulo recursive functions, a framework for deductive synthesis, and complete synt ...

2013

Function computation via subspace coding

Christina Fragouli, Lorenzo Keller, Nikhil Karamchandani

This paper considers function computation in a network where intermediate nodes perform randomized network coding, through appropriate choice of the subspace codebooks at the source nodes. Unlike traditional network coding for comput- ing functions, that r ...

2013

THE NUMBER OF EDGES IN k-QUASI-PLANAR GRAPHS

János Pach

A graph drawn in the plane is called k-quasi-planar if it does not contain k pair-wise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best k ...

SIAM Publications2013

Integrated Kernel Partitioning and Scheduling for Coarse-Grained Reconfigurable Arrays

Giovanni Ansaloni

Coarse-grained reconfigurable arrays (CGRAs) are a promising class of architectures conjugating flexibility and efficiency. Devising effective methodologies to map applications onto CGRAs is a challenging task, due to their parallel execution paradigm and ...

Institute of Electrical and Electronics Engineers2012