All reports by Author Frederic Magniez:

__
TR16-150
| 23rd September 2016
__

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez#### Streaming Communication Protocols

__
TR15-104
| 13th May 2015
__

Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont#### Streaming Property Testing of Visibly Pushdown Languages

Revisions: 2

__
TR12-128
| 21st September 2012
__

Nathanaël François, Frederic Magniez#### Streaming Complexity of Checking Priority Queues

Revisions: 1

__
TR10-192
| 8th December 2010
__

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao#### Improved bounds for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR09-119
| 17th November 2009
__

Frederic Magniez, Claire Mathieu, Ashwin Nayak#### Recognizing well-parenthesized expressions in the streaming model

__
TR04-096
| 4th November 2004
__

Eldar Fischer, Frederic Magniez, Michel de Rougemont#### Property and Equivalence Testing on Strings

Revisions: 1

__
TR01-051
| 4th May 2001
__

Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont#### Probabilistic abstraction for model checking: An approach based on property testing

Revisions: 1

__
TR01-014
| 7th February 2001
__

Marcos Kiwi, Frederic Magniez, Miklos Santha#### Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents ... more >>>

Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont

In the context of language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al, a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs ... more >>>

Nathanaël François, Frederic Magniez

This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure. In ... more >>>

Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

Frederic Magniez, Claire Mathieu, Ashwin Nayak

Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis.

We present a one-pass randomized streaming ... more >>>

Eldar Fischer, Frederic Magniez, Michel de Rougemont

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>

Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont

In model checking, program correctness on all inputs is verified

by considering the transition system underlying a given program.

In practice, the system can be intractably large.

In property testing, a property of a single input is verified

by looking at a small subset of that input.

We ...
more >>>

Marcos Kiwi, Frederic Magniez, Miklos Santha

In the late 80's Blum, Luby, Rubinfeld, Kannan et al. pioneered

the theory of self-testing as an alternative way of dealing with

the problem of software reliability.

Over the last decade this theory played a crucial role in

the construction of probabilistically checkable proofs and

the ...
more >>>