Publications associées à Fast Randomized Test-and-Set and Renaming

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

String Matching: Communication, Circuits, and Learning

Mika Tapani Göös

String matching is the problem of deciding whether a given n-bit string contains a given k-bit pattern. We study the complexity of this problem in three settings. - Communication complexity. For small k, we provide near-optimal upper and lower bounds on th ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2019

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Serge Vaudenay, Fatma Betül Durak

Feistel Networks (FN) are now being used massively to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when ...

ePrint2018

SAT-Based Area Recovery in Structural Technology Mapping

Bruno Schmitt Antunes

This paper proposes a fast SAT-based algorithm for recovering area applicable to an already technology mapped circuit. The algorithm considers a sequence of relatively small overlapping regions, called windows, in a mapped network and tries to improve the ...

ASSOC COMPUTING MACHINERY2018

A Comment on “Computational Complexity of Stochastic Programming Problems”

Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann

Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Mathematical Programming A, 106(3):423–432, 200 ...

Springer Heidelberg2016

Convex block-sparse linear regression with expanders - provably

Volkan Cevher, Quoc Tran Dinh, Anastasios Kyrillidis, Luca Baldassarre, Bubacarr Bah

Sparse matrices are favorable objects in machine learning and optimization. When such matrices are used, in place of dense ones, the overall complexity requirements in optimization can be significantly reduced in practice, both in terms of space and run-ti ...

2016

Incremental View Maintenance for Collection Programming

Christoph Koch, Daniel Lupei, Val Tannen

In the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update the ...

ACM2016

A Composition Theorem for Conical Juntas

Mika Tapani Göös

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2016

Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme

Boi Faltings, Immanuel Trummer

The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A s ...

Institute of Electrical and Electronics Engineers2014

Tight Bounds for Asynchronous Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual ...

Association for Computing Machinery2014

Fast Randomized Test-and-Set and Renaming

Graph Chatbot

Chattez avec Graph Search