Publication

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

Related publications (37)

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.

New Hardness Results for Diophantine Approximation

Friedrich Eisenbrand, Thomas Rothvoss

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...

Springer2009

On the n-dimensional Dirichlet problem for isometric maps

Bernard Dacorogna

We exhibit explicit Lipschitz maps from R '' to R '' which have almost everywhere orthogonal gradient and are equal to zero on the boundary of a cube. We solve the problem by induction on the dimension n. (C) 2008 Elsevier Inc. All rights reserved. ...

2008

A Scalable Method for Multiagent Constraint Optimization

Boi Faltings, Adrian Petcu

We present in this paper a new complete method for distributed constraint optimization. This is a utility-propagation method, inspired by the sum-product algorithm (Kschischang et al 2001). The original algorithm requires fixed message sizes, linear memory ...

2005

Networked Slepian-Wolf: Theory and Algorithms

Martin Vetterli, Razvan Cristescu

In this paper, we consider the minimization of a relevant energy consumption related cost function in the context of sensor networks where correlated sources are generated at various sets of source nodes and have to be transmitted to some set of sink nodes ...

Springer Verlag2004

Networked Slepian-Wolf: Theory and Algorithms

Martin Vetterli, Razvan Cristescu

2004

Power Efficient Gathering of Correlated Data: Optimization, NP-Completeness and Heuristics

Martin Vetterli, Razvan Cristescu

This paper studies the interaction between the communication costs in a sensor network and the structure of the data that it measures. We formulate an optimization problem definition for power efficient data gathering and assess its computational difficult ...

2003

Using the Breakout Algorithm to Identify Hard and Unsolvable Subproblems

Boi Faltings, Carlos Eisenberg

Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for highly constrained or overconstrained ...

Swiss Federal Institute of Technology (EPFL)2003