Publications related to Computational complexity of mathematical operations

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

David Atienza Alonso, Giovanni Ansaloni, Grégoire Axel Eggermann, Marco Antonio Rios

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

New York2023

Why computational complexity may set impenetrable barriers for epistemic reductionism

Michael Herzog, Christian Sachse, Adrien Christophe Doerig

According to physicalism, everything is physical or metaphysically connected to the physical. If physicalism were true, it seems that we should - in principle - be able to reduce the descriptions and explanations of special sciences to physical ones, for e ...

Springer2023

Differentially Private Release of Synthetic Graphs

Mikhail Kapralov, Marek Elias

We propose a (epsilon, delta)-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G' approximating all cuts of the input graph up to an additive error of O (root mn/epsil ...

ASSOC COMPUTING MACHINERY2020

Block-Floating-Point Enhanced MMSE Filter Matrix Computation for MIMO-OFDM Communication Systems

Andreas Peter Burg, Carl Christian Sten Dominic Senning

n this paper we present an architecture for an MMSE ﬁlter matrix computation unit for signal detection in MIMO-OFDM communication systems. We propose to compute the required matrix inverse based on a Cholesky decomposition, followed by a Gauss-Jordan matri ...

2013

Interactive multiview video system with low decoding complexity

Pascal Frossard, Thomas Maugey

Research in multimedia is always investigating new ways of improving the immersive experience of the users. One current solution consists in designing systems which offer a high level of interactivity, such as multiview content navigation where the point o ...

2011

Refined quorum systems

Rachid Guerraoui, Marko Vukolic

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contenti ...

2010

Reverse Search for Parametric Linear Programming

Colin Neil Jones

This paper introduces a new enumeration technique for (multi)parametric linear programs (pLPs) based on the reverse-search paradigm. We prove that the proposed algorithm has a computational complexity that is linear in the size of the output (number of so- ...

IEEE2006