BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Frederic Magniez

Frederic Magniez appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational Complexityquant-phComputer Science and Game TheoryDatabasesDistributed, Parallel, and Cluster Computing

Catalog footprint

What is connected

11works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

Quantum Distributed Complexity of Set Disjointness on a Line

Set Disjointness on a Line is a variant of the Set Disjointness problem in a distributed computing scenario with $d+1$ processors arranged on a path of length $d$. It was introduced by Le Gall and Magniez (PODC 2018) for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path consists of O$( \log n)$ qubits for $n$-bit inputs. We prove an unconditional lower bound of $\widetildeΩ\big(\sqrt[3]{n d^2}+\sqrt{n} \, \big)$ rounds for Set Disjointness on a Line with $d + 1$ processors. The result gives us a new lower bound of $\widetildeΩ \big( \sqrt[3]{nδ^2}+\sqrt{n} \, \big)$ on the number of rounds required for computing the diameter $δ$ of any $n$-node network with quantum messages of size O$(\log n)$ in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal parallel quantum query algorithms

We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithms as much as possible. We show tight bounds for a number of problems, specifically Theta((n/p)^{2/3}) p-parallel queries for element distinctness and Theta((n/p)^{k/(k+1)} for k-sum. Our upper bounds are obtained by parallelized quantum walk algorithms, and our lower bounds are based on a relatively small modification of the adversary lower bound method, combined with recent results of Belovs et al. on learning graphs. We also prove some general bounds, in particular that quantum and classical p-parallel complexity are polynomially related for all total functions f when p is small compared to f's block sensitivity.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Unidirectional Input/Output Streaming Complexity of Reversal and Sorting

We consider unidirectional data streams with restricted access, such as read-only and write-only streams. For read-write streams, we also introduce a new complexity measure called expansion, the ratio between the space used on the stream and the input size. We give tight bounds for the complexity of reversing a stream of length $n$ in several of the possible models. In the read-only and write-only model, we show that $p$-pass algorithms need memory space $Θ(n/p)$. But if either the output stream or the input stream is read-write, then the complexity falls to $Θ(n/p^2)$. It becomes $polylog(n)$ if $p = O(log n)$ and both streams are read-write. We also study the complexity of sorting a stream and give two algorithms with small expansion. Our main sorting algorithm is randomized and has $O(1)$ expansion, $O(log n)$ passes and $O(log n)$ memory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates

We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound (obtained via learning graphs) up to log factors. Furthermore, our algorithm has time complexity ~O(n^{5/7}), improving the previous ~O(n^{3/4}).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improved bounds for the randomized decision tree complexity of recursive majority

We consider the randomized decision tree complexity of the recursive 3-majority function. We prove a lower bound of $(1/2-δ) \cdot 2.57143^h$ for the two-sided-error randomized decision tree complexity of evaluating height $h$ formulae with error $δ\in [0,1/2)$. This improves the lower bound of $(1-2δ)(7/3)^h$ given by Jayram, Kumar, and Sivakumar (STOC'03), and the one of $(1-2δ) \cdot 2.55^h$ given by Leonardos (ICALP'13). Second, we improve the upper bound by giving a new zero-error randomized decision tree algorithm that has complexity at most $(1.007) \cdot 2.64944^h$. The previous best known algorithm achieved complexity $(1.004) \cdot 2.65622^h$. The new lower bound follows from a better analysis of the base case of the recursion of Jayram et al. The new algorithm uses a novel "interleaving" of two recursive algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A learning graph based quantum query algorithm for finding constant-size subgraphs

Let $H$ be a fixed $k$-vertex graph with $m$ edges and minimum degree $d >0$. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an $n$-vertex graph contains $H$ as a subgraph is $O(n^{2-2/k-t})$, where $ t = \max{\frac{k^2- 2(m+1)}{k(k+1)(m+1)}, \frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity $\widetilde O(n^{2-2/k})$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

We show that the quantum query complexity of detecting if an $n$-vertex graph contains a triangle is $O(n^{9/7})$. This improves the previous best algorithm of Belovs making $O(n^{35/27})$ queries. For the problem of determining if an operation $\circ : S \times S \rightarrow S$ is associative, we give an algorithm making $O(|S|^{10/7})$ queries, the first improvement to the trivial $O(|S|^{3/2})$ application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work, the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Nested Quantum Walks with Quantum Data Structures

We develop a new framework that extends the quantum walk framework of Magniez, Nayak, Roland, and Santha, by utilizing the idea of quantum data structures to construct an efficient method of nesting quantum walks. Surprisingly, only classical data structures were considered before for searching via quantum walks. The recently proposed learning graph framework of Belovs has yielded improved upper bounds for several problems, including triangle finding and more general subgraph detection. We exhibit the power of our framework by giving a simple explicit constructions that reproduce both the $O(n^{35/27})$ and $O(n^{9/7})$ learning graph upper bounds (up to logarithmic factors) for triangle finding, and discuss how other known upper bounds in the original learning graph framework can be converted to algorithms in our framework. We hope that the ease of use of this framework will lead to the discovery of new upper bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Streaming Complexity of Checking Priority Queues

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 a context of massive data, one would like to minimize both the amount of reliable memory of the checker and the number of passes on the sequence of operations. Chu, Kannan and McGregor initiated the study of checking priority queues in this setting. They showed that use of timestamps allows to check a priority queue with a single pass and memory space O(N^(1/2)), up to a polylogarithmic factor. Later, Chakrabarti, Cormode, Kondapally and McGregor removed the use of timestamps, and proved that more passes do not help. We show that, even in the presence of timestamps, more passes do not help, solving a previously open problem. On the other hand, we show that a second pass, but in reverse direction, shrinks the memory space to O((log N)^2), extending a phenomenon the first time observed by Magniez, Mathieu and Nayak for checking well-parenthesized expressions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The complexity of approximate Nash equilibrium in congestion games with negative delays

We extend the study of the complexity of finding an $\eps$-approximate Nash equilibrium in congestion games from the case of positive delay functions to delays of arbitrary sign. We first prove that in symmetric games with $α$-bounded jump the $\eps$-Nash dynamic converges in polynomial time when all delay functions are negative, similarly to the case of positive delays. We then establish a hardness result for symmetric games with $α$-bounded jump and with arbitrary delay functions: in that case finding an $\eps$-Nash equilibrium becomes $\PLS$-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Validating XML Documents in the Streaming Model with External Memory

We study the problem of validating XML documents of size $N$ against general DTDs in the context of streaming algorithms. The starting point of this work is a well-known space lower bound. There are XML documents and DTDs for which $p$-pass streaming algorithms require $Ω(N/p)$ space. We show that when allowing access to external memory, there is a deterministic streaming algorithm that solves this problem with memory space $O(\log^2 N)$, a constant number of auxiliary read/write streams, and $O(\log N)$ total number of passes on the XML document and auxiliary streams. An important intermediate step of this algorithm is the computation of the First-Child-Next-Sibling (FCNS) encoding of the initial XML document in a streaming fashion. We study this problem independently, and we also provide memory efficient streaming algorithms for decoding an XML document given in its FCNS encoding. Furthermore, validating XML documents encoding binary trees in the usual streaming model without external memory can be done with sublinear memory. There is a one-pass algorithm using $O(\sqrt{N \log N})$ space, and a bidirectional two-pass algorithm using $O(\log^2 N)$ space performing this task.

0 citations0 reviewsNo code linkedOpen access