DROPS

Document

Developmental Machine Learning: From Human Learning to Machines and Back (Dagstuhl Seminar 22422)

Authors: James M. Rehg, Pierre-Yves Oudeyer, Linda B. Smith, Sho Tsuji, Stefan Stojanov, and Ngoc Anh Thai

Published in: Dagstuhl Reports, Volume 12, Issue 10 (2023)

Abstract

This interdisciplinary seminar brought together 18 academic and industry computer science researchers in artificial intelligence, computer vision and machine learning with 19 researchers from developmental psychology, neuroscience and linguistics. The objective was to catalyze connections between these communities, through discussions on both how the use of developmental insights can spur advances in machine learning, and how computational models and data-driven learning can lead to novel tools and insights for studying child development. The seminar consisted of tutorials, working groups, and a series of talks and discussion sessions. The main outcomes of this seminar were 1) The founding of DevelopmentalAI (http://www.developmentalai.com), an online research community to serve as a venue for communication and collaboration between develpomental and machine learning researchers, as well as a place collect and organize relevant research papers and talks; 2) Working group outputs - summaries of in-depth discussions on research questions at the intersection of developmental and machine learning, including the role of information bottlenecks and multimodality, as well as proposals for novel developmentally motivated benchmarks.

Cite as

James M. Rehg, Pierre-Yves Oudeyer, Linda B. Smith, Sho Tsuji, Stefan Stojanov, and Ngoc Anh Thai. Developmental Machine Learning: From Human Learning to Machines and Back (Dagstuhl Seminar 22422). In Dagstuhl Reports, Volume 12, Issue 10, pp. 143-165, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{rehg_et_al:DagRep.12.10.143,
  author =	{Rehg, James M. and Oudeyer, Pierre-Yves and Smith, Linda B. and Tsuji, Sho and Stojanov, Stefan and Thai, Ngoc Anh},
  title =	{{Developmental Machine Learning: From Human Learning to Machines and Back (Dagstuhl Seminar 22422)}},
  pages =	{143--165},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{10},
  editor =	{Rehg, James M. and Oudeyer, Pierre-Yves and Smith, Linda B. and Tsuji, Sho and Stojanov, Stefan and Thai, Ngoc Anh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.10.143},
  URN =		{urn:nbn:de:0030-drops-178247},
  doi =		{10.4230/DagRep.12.10.143},
  annote =	{Keywords: developmental psychology, human learning, machine learning, computer vision, language learning}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2016.15

Design Patterns in Beeping Algorithms

Authors: Arnaud Casteigts, Yves Métivier, John Michael Robson, and Akka Zemmari

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract

We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn, which we refer to as the BL variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Stronger variants exist where the nodes can also detect collision while they are beeping (B_{cd}L) or listening (BL_{cd}), or both (B_{cd}L_{cd}). Beeping models are weak in essence and even simple tasks are difficult or unfeasible with them. This paper starts with a discussion on generic building blocks (design patterns) which seem to occur frequently in the design of beeping algorithms. They include multi-slot phases: the fact of dividing the main loop into a number of specialised slots; exclusive beeps: having a single node beep at a time in a neighbourhood (within one or two hops); adaptive probability: increasing or decreasing the probability of beeping to produce more exclusive beeps; internal (resp. peripheral) collision detection: for detecting collision while beeping (resp. listening); and emulation of collision detection: for enabling this feature when it is not available as a primitive. We then provide algorithms for a number of basic problems, including colouring, 2-hop colouring, degree computation, 2-hop MIS, and collision detection (in BL). Using the patterns, we formulate these algorithms in a rather concise and elegant way. Their analyses (in the full version) are more technical, e.g. one of them relies on a Martingale technique with non-independent variables; another improves that of the MIS algorithm (P. Jeavons et al.) by getting rid of a gigantic constant (the asymptotic order was already optimal). Finally, we study the relative power of several variants of beeping models. In particular, we explain how every Las Vegas algorithm with collision detection can be converted, through emulation, into a Monte Carlo algorithm without, at the cost of a logarithmic slowdown. We prove that this slowdown is optimal up to a constant factor by giving a matching lower bound.

Cite as

Arnaud Casteigts, Yves Métivier, John Michael Robson, and Akka Zemmari. Design Patterns in Beeping Algorithms. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.OPODIS.2016.15,
  author =	{Casteigts, Arnaud and M\'{e}tivier, Yves and Robson, John Michael and Zemmari, Akka},
  title =	{{Design Patterns in Beeping Algorithms}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.15},
  URN =		{urn:nbn:de:0030-drops-70840},
  doi =		{10.4230/LIPIcs.OPODIS.2016.15},
  annote =	{Keywords: Beeping models, Design patterns, Collision detection, Colouring, 2-hop colouring, Degree computation, Emulation}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2449

AMS Without 4-Wise Independence on Product Domains

Authors: Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, and Rafail Ostrovsky

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

In their seminal work, Alon, Matias, and Szegedy introduced several sketching techniques, including showing that $4$-wise independence is sufficient to obtain good approximations of the second frequency moment. In this work, we show that their sketching technique can be extended to product domains $[n]^k$ by using the product of $4$-wise independent functions on $[n]$. Our work extends that of Indyk and McGregor, who showed the result for $k = 2$. Their primary motivation was the problem of identifying correlations in data streams. In their model, a stream of pairs $(i,j) \in [n]^2$ arrive, giving a joint distribution $(X,Y)$, and they find approximation algorithms for how close the joint distribution is to the product of the marginal distributions under various metrics, which naturally corresponds to how close $X$ and $Y$ are to being independent. By using our technique, we obtain a new result for the problem of approximating the $\ell_2$ distance between the joint distribution and the product of the marginal distributions for $k$-ary vectors, instead of just pairs, in a single pass. Our analysis gives a randomized algorithm that is a $(1\pm \epsilon)$ approximation (with probability $1-\delta$) that requires space logarithmic in $n$ and $m$ and proportional to $3^k$.

Cite as

Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, and Rafail Ostrovsky. AMS Without 4-Wise Independence on Product Domains. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 119-130, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.STACS.2010.2449,
  author =	{Braverman, Vladimir and Chung, Kai-Min and Liu, Zhenming and Mitzenmacher, Michael and Ostrovsky, Rafail},
  title =	{{AMS Without 4-Wise Independence on Product Domains}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{119--130},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2449},
  URN =		{urn:nbn:de:0030-drops-24496},
  doi =		{10.4230/LIPIcs.STACS.2010.2449},
  annote =	{Keywords: Data Streams, Randomized Algorithms, Streaming Algorithms, Independence, Sketches}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2496

Optimal Query Complexity for Reconstructing Hypergraphs

Authors: Nader H. Bshouty and Hanna Mazzawi

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

In this paper we consider the problem of reconstructing a hidden weighted hypergraph of constant rank using additive queries. We prove the following: Let $G$ be a weighted hidden hypergraph of constant rank with~$n$ vertices and $m$ hyperedges. For any $m$ there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O\left(\frac{m\log n}{\log m}\right) $$ additive queries. This solves the open problem in [S. Choi, J. H. Kim. Optimal Query Complexity Bounds for Finding Graphs. {\em STOC}, 749--758, 2008]. When the weights of the hypergraph are integers that are less than $O(poly(n^d/m))$ where $d$ is the rank of the hypergraph (and therefore for unweighted hypergraphs) there exists a non-adaptive algorithm that finds the edges of the graph and their weights using $$ O\left(\frac{m\log \frac{n^d}{m}}{\log m}\right). $$ additive queries. Using the information theoretic bound the above query complexities are tight.

Cite as

Nader H. Bshouty and Hanna Mazzawi. Optimal Query Complexity for Reconstructing Hypergraphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 143-154, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.STACS.2010.2496,
  author =	{Bshouty, Nader H. and Mazzawi, Hanna},
  title =	{{Optimal Query Complexity for Reconstructing Hypergraphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{143--154},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2496},
  URN =		{urn:nbn:de:0030-drops-24968},
  doi =		{10.4230/LIPIcs.STACS.2010.2496},
  annote =	{Keywords: Query complexity, hypergraphs}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2461

Intrinsic Universality in Self-Assembly

Authors: David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

We show that the Tile Assembly Model exhibits a strong notion of universality where the goal is to give a single tile assembly system that simulates the behavior of any other tile assembly system. We give a tile assembly system that is capable of simulating a very wide class of tile systems, including itself. Specifically, we give a tile set that simulates the assembly of any tile assembly system in a class of systems that we call \emph{locally consistent}: each tile binds with exactly the strength needed to stay attached, and that there are no glue mismatches between tiles in any produced assembly. Our construction is reminiscent of the studies of \emph{intrinsic universality} of cellular automata by Ollinger and others, in the sense that our simulation of a tile system $T$ by a tile system $U$ represents each tile in an assembly produced by $T$ by a $c \times c$ block of tiles in $U$, where $c$ is a constant depending on $T$ but not on the size of the assembly $T$ produces (which may in fact be infinite). Also, our construction improves on earlier simulations of tile assembly systems by other tile assembly systems (in particular, those of Soloveichik and Winfree, and of Demaine et al.) in that we simulate the actual process of self-assembly, not just the end result, as in Soloveichik and Winfree's construction, and we do not discriminate against infinite structures. Both previous results simulate only temperature 1 systems, whereas our construction simulates tile assembly systems operating at temperature 2.

Cite as

David Doty, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers, and Damien Woods. Intrinsic Universality in Self-Assembly. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.STACS.2010.2461,
  author =	{Doty, David and Lutz, Jack H. and Patitz, Matthew J. and Summers, Scott M. and Woods, Damien},
  title =	{{Intrinsic Universality in Self-Assembly}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{275--286},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2461},
  URN =		{urn:nbn:de:0030-drops-24619},
  doi =		{10.4230/LIPIcs.STACS.2010.2461},
  annote =	{Keywords: Biological computing, Molecular computation, intrinsic universality, self-assembly}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2462

Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses

Authors: Xiaoyang Gu, John M. Hitchcock, and Aduri Pavan

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

This paper presents the following results on sets that are complete for $\NP$. \begin{enumerate} \item If there is a problem in $\NP$ that requires $\twonO$ time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. \item If there is a problem in $\CoNP$ that cannot be solved by polynomial-size nondeterministic circuits, then every many-one complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. \item If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in $\NP \cap \CoNP$, then there is a Turing complete language for $\NP$ that is not many-one complete. \end{enumerate} Our first two results use worst-case hardness hypotheses whereas earlier work that showed similar results relied on average-case or almost-everywhere hardness assumptions. The use of average-case and worst-case hypotheses in the last result is unique as previous results obtaining the same consequence relied on almost-everywhere hardness results.

Cite as

Xiaoyang Gu, John M. Hitchcock, and Aduri Pavan. Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 429-440, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{gu_et_al:LIPIcs.STACS.2010.2462,
  author =	{Gu, Xiaoyang and Hitchcock, John M. and Pavan, Aduri},
  title =	{{Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{429--440},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2462},
  URN =		{urn:nbn:de:0030-drops-24627},
  doi =		{10.4230/LIPIcs.STACS.2010.2462},
  annote =	{Keywords: Computational complexity, NP-completeness}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2477

Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion

Authors: Maurice Jansen

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

Kabanets and Impagliazzo \cite{KaIm04} show how to decide the circuit polynomial identity testing problem (CPIT) in deterministic subexponential time, assuming hardness of some explicit multilinear polynomial family $\{f_m\}_{m \geq 1}$ for arithmetic circuits. In this paper, a special case of CPIT is considered, namely non-singular matrix completion ($\NSMC$) under a low-individual-degree promise. For this subclass of problems it is shown how to obtain the same deterministic time bound, using a weaker assumption in terms of the {\em determinantal complexity} $\dcomp(f_m)$ of $f_m$. Building on work by Agrawal \cite{Agr05}, hardness-randomness tradeoffs will also be shown in the converse direction, in an effort to make progress on Valiant's $\VP$ versus $\VNP$ problem. To separate $\VP$ and $\VNP$, it is known to be sufficient to prove that the determinantal complexity of the $m\times m$ permanent is $m^{\omega(\log m)}$. In this paper it is shown, for an appropriate notion of explicitness, that the existence of an explicit multilinear polynomial family $\{f_m\}_{m \geq 1}$ with $\dcomp(f_m) = m^{\omega(\log m)}$ is equivalent to the existence of an efficiently computable {\em generator} $\{G_n\}_{n\geq 1}$ {\em for} multilinear $\NSMC$ with seed length $O(n^{1/\sqrt{\log n}})$. The latter is a combinatorial object that provides an efficient deterministic black-box algorithm for $\NSMC$. ``Multilinear $\NSMC$'' indicates that $G_n$ only has to work for matrices $M(x)$ of $poly(n)$ size in $n$ variables, for which $\det(M(x))$ is a multilinear polynomial.

Cite as

Maurice Jansen. Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 465-476, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jansen:LIPIcs.STACS.2010.2477,
  author =	{Jansen, Maurice},
  title =	{{Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{465--476},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2477},
  URN =		{urn:nbn:de:0030-drops-24770},
  doi =		{10.4230/LIPIcs.STACS.2010.2477},
  annote =	{Keywords: Computational complexity, arithmetic circuits, hardness-randomness tradeoffs, identity testing, determinant versus permanent}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2478

On Equations over Sets of Integers

Authors: Artur Jez and Alexander Okhotin

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition $S+T=\makeset{m+n}{m \in S, \: n \in T}$ and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction $S \dotminus T=\makeset{m-n}{m \in S, \: n \in T, \: m \geqslant n}$. Testing whether a given system has a solution is $\Sigma^1_1$-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.

Cite as

Artur Jez and Alexander Okhotin. On Equations over Sets of Integers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 477-488, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2010.2478,
  author =	{Jez, Artur and Okhotin, Alexander},
  title =	{{On Equations over Sets of Integers}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{477--488},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2478},
  URN =		{urn:nbn:de:0030-drops-24780},
  doi =		{10.4230/LIPIcs.STACS.2010.2478},
  annote =	{Keywords: Language equations, computability, arithmetical hierarchy, hyper-arithmetical hierarchy}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2484

An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem

Authors: François Le Gall

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

In this paper we consider the problem of testing whether two finite groups are isomorphic. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. Le Gall has constructed an efficient classical algorithm for a class of groups corresponding to one of the most natural ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group $A$ by a cyclic group $\Int_m$ with the order of $A$ coprime with $m$. More precisely, the running time of that algorithm is almost linear in the order of the input groups. In this paper we present a \emph{quantum} algorithm solving the same problem in time polynomial in the \emph{logarithm} of the order of the input groups. This algorithm works in the black-box setting and is the first quantum algorithm solving instances of the nonabelian group isomorphism problem exponentially faster than the best known classical algorithms.

Cite as

François Le Gall. An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 549-560, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{legall:LIPIcs.STACS.2010.2484,
  author =	{Le Gall, Fran\c{c}ois},
  title =	{{An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{549--560},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2484},
  URN =		{urn:nbn:de:0030-drops-24843},
  doi =		{10.4230/LIPIcs.STACS.2010.2484},
  annote =	{Keywords: Quantum algorithms, group isomorphism problem, black-box groups}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2489

Relaxed Spanners for Directed Disk Graphs

Authors: David Peleg and Liam Roditty

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

Let $(V,\delta)$ be a finite metric space, where $V$ is a set of $n$ points and $\delta$ is a distance function defined for these points. Assume that $(V,\delta)$ has a constant doubling dimension $d$ and assume that each point $p\in V$ has a disk of radius $r(p)$ around it. The disk graph that corresponds to $V$ and $r(\cdot)$ is a \emph{directed} graph $I(V,E,r)$, whose vertices are the points of $V$ and whose edge set includes a directed edge from $p$ to $q$ if $\delta(p,q)\leq r(p)$. In~\cite{PeRo08} we presented an algorithm for constructing a $(1+\eps)$-spanner of size $O(n/\eps^d \log M)$, where $M$ is the maximal radius $r(p)$. The current paper presents two results. The first shows that the spanner of~\cite{PeRo08} is essentially optimal, i.e., for metrics of constant doubling dimension it is not possible to guarantee a spanner whose size is independent of $M$. The second result shows that by slightly relaxing the requirements and allowing a small perturbation of the radius assignment, considerably better spanners can be constructed. In particular, we show that if it is allowed to use edges of the disk graph $I(V,E,r_{1+\eps})$, where $r_{1+\eps}(p) = (1+\eps)\cdot r(p)$ for every $p\in V$, then it is possible to get a $(1+\eps)$-spanner of size $O(n/\eps^d)$ for $I(V,E,r)$. Our algorithm is simple and can be implemented efficiently.

Cite as

David Peleg and Liam Roditty. Relaxed Spanners for Directed Disk Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 609-620, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{peleg_et_al:LIPIcs.STACS.2010.2489,
  author =	{Peleg, David and Roditty, Liam},
  title =	{{Relaxed Spanners for Directed Disk Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{609--620},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2489},
  URN =		{urn:nbn:de:0030-drops-24898},
  doi =		{10.4230/LIPIcs.STACS.2010.2489},
  annote =	{Keywords: Spanners, directed graphs}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2491

Construction Sequences and Certifying 3-Connectedness

Authors: Jens M. Schmidt

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

Given two $3$-connected graphs $G$ and $H$, a \emph{construction sequence} constructs $G$ from $H$ (e.\,g. from the $K_4$) with three basic operations, called the \emph{Barnette-Gr\"unbaum operations}. These operations are known to be able to construct all $3$-connected graphs. We extend this result by identifying every intermediate graph in the construction sequence with a subdivision in $G$ and showing under some minor assumptions that there is still a construction sequence to $G$ when we start from an \emph{arbitrary prescribed} $H$-subdivision. This leads to the first algorithm that computes a construction sequence in time $O(|V(G)|^2)$. As an application, we develop a certificate for the $3$-connectedness of graphs that can be easily computed and verified. Based on this, a certifying test on $3$-connectedness is designed.%Finding certifying algorithms is a major goal for problems where the efficient solutions known are complicated. Tutte proved that every $3$-connected graph on more than $4$ nodes has a \emph{contractible edge}. Barnette and Gr\"unbaum proved the existence of a \emph{removable edge} in the same setting. We show that the sequence of contractions and the sequence of removals from $G$ to the $K_4$ can be computed in $O(|V|^2)$ time by extending Barnette and Gr\"unbaum's theorem. As an application, we derive a certificate for the $3$-connectedness of graphs that can be easily computed and verified.

Cite as

Jens M. Schmidt. Construction Sequences and Certifying 3-Connectedness. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 633-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{schmidt:LIPIcs.STACS.2010.2491,
  author =	{Schmidt, Jens M.},
  title =	{{Construction Sequences and Certifying 3-Connectedness}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{633--644},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2491},
  URN =		{urn:nbn:de:0030-drops-24918},
  doi =		{10.4230/LIPIcs.STACS.2010.2491},
  annote =	{Keywords: Construction sequence, 3-connected graph, nested subdivisions, inductive characterization, 3-connectedness, certifying algorithm}
}

Document

DOI: 10.4230/LIPIcs.STACS.2009.1813

Locally Decodable Quantum Codes

Authors: Jop Briet and Ronald de Wolf

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

We study a quantum analogue of locally decodable error-correcting codes. A $q$-query \emph{locally decodable quantum code} encodes $n$ classical bits in an $m$-qubit state, in such a way that each of the encoded bits can be recovered with high probability by a measurement on at most $q$ qubits of the quantum code, even if a constant fraction of its qubits have been corrupted adversarially. We show that such a quantum code can be transformed into a \emph{classical} $q$-query locally decodable code of the same length that can be decoded well on average (albeit with smaller success probability and noise-tolerance). This shows, roughly speaking, that $q$-query quantum codes are not significantly better than $q$-query classical codes, at least for constant or small $q$.

Cite as

Jop Briet and Ronald de Wolf. Locally Decodable Quantum Codes. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 219-230, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{briet_et_al:LIPIcs.STACS.2009.1813,
  author =	{Briet, Jop and de Wolf, Ronald},
  title =	{{Locally Decodable Quantum Codes}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{219--230},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1813},
  URN =		{urn:nbn:de:0030-drops-18134},
  doi =		{10.4230/LIPIcs.STACS.2009.1813},
  annote =	{Keywords: Data structures, Locally decodable codes, Quantum computing}
}

Document

DOI: 10.4230/LIPIcs.STACS.2009.1803

Approximating Acyclicity Parameters of Sparse Hypergraphs

Authors: Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx in SODA'06, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending tractability of many problems in database theory and artificial intelligence. Computing each of these width parameters is known to be an NP-hard problem. Moreover, the (generalized) hypertree width of an n-vertex hypergraph cannot be approximated within a logarithmic factor unless P=NP. In this paper, we study the approximability of (generalized, fractional) hyper treewidth of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph is constant-factor sandwiched by the treewidth of its incidence graph, when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some H-minor-free graph class. This extends the results of Feige, Hajiaghayi, and Lee from STOC'05 on approximating treewidth of H-minor-free graphs.

Cite as

Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Approximating Acyclicity Parameters of Sparse Hypergraphs. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 445-456, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.STACS.2009.1803,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Thilikos, Dimitrios M.},
  title =	{{Approximating Acyclicity Parameters of Sparse Hypergraphs}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{445--456},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1803},
  URN =		{urn:nbn:de:0030-drops-18034},
  doi =		{10.4230/LIPIcs.STACS.2009.1803},
  annote =	{Keywords: Graph, Hypergraph, Hypertree width, Treewidth}
}

Document

DOI: 10.4230/LIPIcs.STACS.2009.1845

Optimal Cache-Aware Suffix Selection

Authors: Gianni Franceschini, Roberto Grossi, and S. Muthukrishnan

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the suffix selection problem in the cache-aware model that captures two-level memory inherent in computing systems, for a \emph{cache} of limited size $M$ and block size $B$. The complexity of interest is the number of block transfers. We present an optimal suffix selection algorithm in the cache-aware model, requiring $\Theta\left(N/B\right)$ block transfers, for any string $S$ over an unbounded alphabet (where characters can only be compared), under the common tall-cache assumption (i.e. $M=\Omega\left(B^{1+\epsilon}\right)$, where $\epsilon<1$). Our algorithm beats the bottleneck bound for permuting an input array to the desired output array, which holds for nearly any nontrivial problem in hierarchical memory models.

Cite as

Gianni Franceschini, Roberto Grossi, and S. Muthukrishnan. Optimal Cache-Aware Suffix Selection. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 457-468, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{franceschini_et_al:LIPIcs.STACS.2009.1845,
  author =	{Franceschini, Gianni and Grossi, Roberto and Muthukrishnan, S.},
  title =	{{Optimal Cache-Aware Suffix Selection}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{457--468},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1845},
  URN =		{urn:nbn:de:0030-drops-18452},
  doi =		{10.4230/LIPIcs.STACS.2009.1845},
  annote =	{Keywords: }
}

Document

DOI: 10.4230/LIPIcs.STACS.2009.1847

More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries

Authors: Roberto Grossi, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

We consider the problem of representing, in a compressed format, a bit-vector~$S$ of $m$ bits with $n$ $\mathbf{1}$s, supporting the following operations, where $b \in \{ \mathbf{0}, \mathbf{1} \}$: \begin{itemize} \item $\mathtt{rank}_b(S,i)$ returns the number of occurrences of bit $b$ in the prefix $S\left[1..i\right]$; \item $\mathtt{select}_b(S,i)$ returns the position of the $i$th occurrence of bit $b$ in $S$. \end{itemize} Such a data structure is called \emph{fully indexable dictionary (\textsc{fid})} [Raman, Raman, and Rao, 2007], and is at least as powerful as predecessor data structures. Viewing $S$ as a set $X = \{ x_1, x_2, \ldots, x_n \}$ of $n$ distinct integers drawn from a universe $[m] = \{1, \ldots, m\}$, the predecessor of integer $y \in [m]$ in $X$ is given by $\ensuremath{\mathtt{select}^{}_1}(S, \ensuremath{\mathtt{rank}_1}(S,y-1))$. {\textsc{fid}}s have many applications in succinct and compressed data structures, as they are often involved in the construction of succinct representation for a variety of abstract data types. Our focus is on space-efficient {\textsc{fid}}s on the \textsc{ram} model with word size $\Theta(\lg m)$ and constant time for all operations, so that the time cost is independent of the input size. Given the bitstring $S$ to be encoded, having length $m$ and containing $n$ ones, the minimal amount of information that needs to be stored is $B(n,m) = \lceil \log {{m}\choose{n}} \rceil$. The state of the art in building a \textsc{fid}\ for~$S$ is given in~\mbox{}[P\v{a}tra\c{s}cu, 2008] using $B(m,n)+O( m / ( (\log m/ t) ^t) ) + O(m^{3/4}) $ bits, to support the operations in $O(t)$ time. Here, we propose a parametric data structure exhibiting a time/space trade-off such that, for any real constants $0 < \delta \leq 1/2$, $0 < \varepsilon \leq 1$, and integer $s > 0$, it uses \[ B(n,m) + O\left(n^{1+\delta} + n \left(\frac{m}{n^s}\right)^\varepsilon\right) \] bits and performs all the operations in time $O(s\delta^{-1} + \varepsilon^{-1})$. The improvement is twofold: our redundancy can be lowered parametrically and, fixing $s = O(1)$, we get a constant-time \textsc{fid}\ whose space is $B(n,m) + O(m^\varepsilon/\mathrm{poly}(n))$ bits, for sufficiently large $m$. This is a significant improvement compared to the previous bounds for the general case.

Cite as

Roberto Grossi, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao. More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 517-528, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{grossi_et_al:LIPIcs.STACS.2009.1847,
  author =	{Grossi, Roberto and Orlandi, Alessio and Raman, Rajeev and Rao, S. Srinivasa},
  title =	{{More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{517--528},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1847},
  URN =		{urn:nbn:de:0030-drops-18470},
  doi =		{10.4230/LIPIcs.STACS.2009.1847},
  annote =	{Keywords: }
}

18 Search Results for "M�tivier, Yves"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message