Concept

Counting problem (complexity)

Related publications (33)

cRacklet: a spectral boundary integral method library for interfacial rupture simulation

Jean-François Molinari, Thibault Didier Roch, Fabian Barras

The study of dynamically propagating rupture along interfaces is of prime importance in various fields and system sizes, including tribology (nm to m), engineering (mm to m) and geophysics (m to km) (Armstrong-Hélouvry et al., 1994; Ben-Zion, 2008; Vanossi ...

2022

A method for faster application of process integration techniques in retrofit situations

Numerous process integration techniques were proved to be highly effective for identifying and estimating potential energy savings in the industry. However, they require high time and effort to collect and analyse process data. As a result, they do not con ...

ELSEVIER SCI LTD2021

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the spec ...

EPFL2021

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

Mika Tapani Göös

We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2020

Second-order sensitivity in the cylinder wake: Optimal spanwise-periodic wall actuation and wall deformation

François Gallaire, Edouard Boujo, Andrea Fani

Two-dimensional (2D) flows can be controlled efficiently using spanwise "waviness," i.e., a control (e.g., wall blowing and suction or wall deformation) that is periodic in the spanwise direction. This study tackles the global linear stability of 2D flows ...

AMER PHYSICAL SOC2019

Coordinate-Descent Diffusion Learning by Networked Agents

Ali H. Sayed, Bicheng Ying, Chengcheng Wang

This paper examines the mean-square error performance of diffusion stochastic algorithms under a generalized coordinate-descent scheme. In this setting, the adaptation step by each agent is limited to a random subset of the coordinates of its stochastic gr ...

Ieee-Inst Electrical Electronics Engineers Inc2018

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov, John Michael Goddard Kallaugher

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...

IEEE COMPUTER SOC2018

Coordinate-descent adaptation over networks

Ali H. Sayed, Bicheng Ying, Chengcheng Wang

This work examines the mean-square error performance of diffusion stochastic algorithms under a generalized coordinate-descent scheme. In this setting, the adaptation step by each agent is limited to a random subset of the coordinates of its stochastic gra ...

2017

Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage

Volkan Cevher, Alp Yurtsever

This paper considers a fundamental class of convex matrix optimization problems with low-rank solutions. We show it is possible to solve these problem using far less memory than the natural size of the decision variable when the problem data has a concise ...

2017

Graph Chatbot

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.