Faster Integer Multiplication

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

By juxtaposing ideas from fractal geometry and dynamical systems, Furstenberg proposed a series of conjectures in the late 1960's that explore the relationship between digit expansions with respect to multiplicatively independent bases. In this work, we in ...

Driven by the demand for real-time processing and the need to minimize latency in AI algorithms, edge computing has experienced remarkable progress. Decision-making AI applications stand out for their heavy reliance on data-centric operations, predominantl ...

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library ...

Logic rewriting is a powerful optimization technique that replaces small sections of a Boolean network with better implementations. Typically, exact synthesis is used to compute optimum replacement on-the-fly, with possible support for Boolean don't cares. ...

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

Factored form is a powerful multi-level representation of a Boolean function that readily translates into an implementation of the function in CMOS technology. In particular, the number of literals in a factored form correlates strongly with the number of ...

State-of-the-art Artificial Intelligence (AI) algorithms, such as graph neural networks and recommendation systems, require floating-point computation of very large matrix multiplications over sparse data. Their execution in resource-constrained scenarios, ...

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search prob ...

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algor ...

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices. In the first part, we consider algorithms for building ...

Logic resynthesis is the problem of finding a dependency function to re-express a given Boolean function in terms of a given set of divisor functions. In this paper, we study logic resynthesis of majority-based circuits, which is motivated by the increasin ...

We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅_{1/n}(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently stro ...

Most logic synthesis algorithms work on graph representations of logic functions with nodes associated with arbitrary logic expressions or simple logic functions and iteratively optimize such graphs. While recent multilevel logic synthesis efforts focused ...

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 ...

Faster Integer Multiplication

Chat with Graph Search

Additive and geometric transversality of fractal sets in the integers

EdgeAI-Aware Design of In-Memory Computing Architectures

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Scalable Logic Rewriting Using Don’t Cares

A ride time-oriented scheduling algorithm for dial-a-ride problems

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Results on Sparse Integer Programming and Geometric Independent Sets

Formula Normalizations in Verification

Approximation Algorithms for Allocation and Network Design

Improving Standard-Cell Design Flow using Factored Form Optimization

A 16-bit Floating-Point Near-SRAM Architecture for Low-power Sparse Matrix-Vector Multiplication

Proofs, Circuits, and Communication

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Approximate CVPp in time 2(0.802n)

Symmetry in design and decoding of polar-like codes

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition

A Majority Lemma for Randomised Query Complexity

Three-Input Gates for Logic Synthesis

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