Publications related to Communication complexity

MATHICSE Technical Report: Fast recovery and approximation of hidden Cauchy structure

We derive an algorithm of optimal complexity which determines whether a given matrix is a Cauchy matrix, and which exactly recovers the Cauchy points defining a Cauchy matrix from the matrix entries. Moreover, we study how to approximate a given matrix by ...

MATHICSE2015

Capacity and Data Complexity in Multidimensional Linear Attack

Serge Vaudenay, Jialin Huang

Multidimensional linear attacks are one of the most powerful variants of linear cryptanalytic techniques now. However, there is no knowledge on the key-dependent capacity and data complexity so far. Their values were assumed to be close to the average valu ...

Springer2015

Beyond One Third Byzantine Failures

Rachid Guerraoui, Anne-Marie Kermarrec, Cheng Wang

The Byzantine agreement problem requires a set of

n

processes to agree on a value sent by a transmitter, despite a subset of

b

processes behaving in an arbitrary, i.e. Byzantine, manner and sending corrupted messages to all processes in the system. It ...

2015

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Yuri Faenza, Gautier Stauffer

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(vertical bar V vertical bar (vertical bar E vertical bar+vertical bar V vertical bar log vertical bar V vertical bar))-time, drastically improvin ...

Assoc Computing Machinery2014

Time–Data Tradeoffs by Aggressive Smoothing

Volkan Cevher

This paper proposes a tradeoff between sample complexity and computation time that applies to statistical estimators based on convex optimization. As the amount of data increases, we can smooth optimization problems more and more aggressively to achieve ac ...

2014

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

Ramsey-Type Results For Semi-Algebraic Relations

János Pach

A k-ary semi-algebraic relation E on R-d is a subset of R-kd, the set of k-tuples of points in R-d, which is determined by a finite number of polynomial inequalities in kd real variables. The description complexity of such a relation is at most t if d, k < ...

Amer Mathematical Soc2014

Heat exchanger network design of large-scale industrial site with layout inspired constraints

François Maréchal, Nasibeh Pouransari

This paper presents a systematic approach for the synthesis of the heat recovery network in total site using a Mixed Integer Linear Programming model. This model returns a near-to-optimal network configuration with minimum utility cost while allows to sele ...

Elsevier2014

Complexity Certification of the Fast Alternating Minimization Algorithm for Linear Model Predictive Control

Colin Neil Jones, Ye Pu, Melanie Nicole Zeilinger

In this paper, the fast alternating minimization algorithm (FAMA) is proposed to solve model predictive control (MPC) problems with polytopic and second-order cone constraints. We extend previous theoretical results of FAMA to a more general case, where co ...

2014

Fast Process Variation Analysis in Nano-Scaled Technologies Using Column-Wise Sparse Parameter Selection

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Majid Yazdani, Hassan Ghasemzadeh Mohammadi

With growing concern about process variation in deeply nano-scaled technologies, parameterized device and circuit modeling is becoming very important for design and verification. However, the high dimensionality of parameter space is a serious modeling cha ...

2014

Communication complexity

Graph Chatbot

Chat with Graph Search

MATHICSE Technical Report: Fast recovery and approximation of hidden Cauchy structure

Capacity and Data Complexity in Multidimensional Linear Attack

Beyond One Third Byzantine Failures

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Time–Data Tradeoffs by Aggressive Smoothing

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

Ramsey-Type Results For Semi-Algebraic Relations

Heat exchanger network design of large-scale industrial site with layout inspired constraints

Complexity Certification of the Fast Alternating Minimization Algorithm for Linear Model Predictive Control

Fast Process Variation Analysis in Nano-Scaled Technologies Using Column-Wise Sparse Parameter Selection

MATHICSE Technical Report: Fast recovery and approximation of hidden Cauchy structure

Heat exchanger network design of large-scale industrial site with layout inspired constraints

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Time–Data Tradeoffs by Aggressive Smoothing

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

Ramsey-Type Results For Semi-Algebraic Relations

Complexity Certification of the Fast Alternating Minimization Algorithm for Linear Model Predictive Control

Fast Process Variation Analysis in Nano-Scaled Technologies Using Column-Wise Sparse Parameter Selection

Beyond One Third Byzantine Failures

Capacity and Data Complexity in Multidimensional Linear Attack