Concept

Parameterized complexity

Related publications (630)

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.

Cocycle growth for the Steinberg representation

Thibaut Dumont

This thesis investigates the growth of the natural cocycle introduced by Klingler for the Steinberg representation. When possible, we extend the framework of simple algebraic groups over a local field to arbitrary Euclidean buildings. In rank one, the grow ...

EPFL2016

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

Pattern formation with voluminous processes

Alexandre David Olivier Maurer

When a shoal of small fishes notices a predator, they typically change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision. This motivates us to design algorithms with similar properties. In this p ...

EPFL2016

Artist-Oriented 3D Character Posing from 2D Strokes

Ronan Boulic, Benoît Le Callennec, Mentar Mahmudi, Pawan Kumar Harish

In this paper we present an intuitive tool suitable for 2D artists using touch-enabled pen tablets. An artist-oriented tool should be easy-to-use, real-time, versatile, and locally refinable. Our approach uses an interactive system for 3D character posing ...

Elsevier2016

Imprecise Security: Quality and Complexity Tradeoffs for Hardware Information Flow Tracking

Paolo Ienne, Andrew James Becker, Ryan Charles Kastner, Wei Hu

Secure hardware design is a challenging task that goes far beyond ensuring functional correctness. Important design properties such as non-interference cannot be verified on functional circuit models due to the lack of essential information (e.g., sensitiv ...

Assoc Computing Machinery2016

Learning Search Strategies from Human Demonstrations

Guillaume Pierre Luc De Chambrier

Decision making and planning with partial state information is a problem faced by all forms of intelligent entities. The formulation of a problem under partial state information leads to an exorbitant set of choices with associated probabilistic outcomes m ...

EPFL2016

Essays on Capital Calculation in Insurance

Mathieu Jacques David Cambou

In order to be able to bear the risk they are taking, insurance companies have to set aside a certain amount of cushion that can guarantee the payment of liabilities, up to a dened probability, and thus to remain solvent in case of bad events. This amount ...

EPFL2016

Phase Transitions in Group Testing

Volkan Cevher, Jonathan Mark Scarlett

The group testing problem consists of determining a sparse subset of a set of items that are ``defective'' based on a set of possibly noisy tests, and arises in areas such as medical testing, fault detection, communication protocols, pattern matching, and ...

2016

Optimal Fair Computation

Rachid Guerraoui, Junxiong Wang

A computation scheme among n parties is fair if no party obtains the computation result unless all other n-1 parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to ...

2016

A Dichotomy for Real Weighted Holant Problems

Sangxia Huang

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can ...

Springer Basel Ag2016