11 Search Results for "Chazelle, Bernard"


Document
Practical Computation of Graph VC-Dimension

Authors: David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)


Abstract
For any set system ℋ = (V,ℛ), ℛ ⊆ 2^V, a subset S ⊆ V is called shattered if every S' ⊆ S results from the intersection of S with some set in ℛ. The VC-dimension of ℋ is the size of a largest shattered set in V. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph G = (V,E), the VC-dimension of G is defined as the VC-dimension of (V, N), where N contains each subset of V that can be obtained as the closed neighborhood of some vertex v ∈ V in G. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the W[1]-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.

Cite as

David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8,
  author =	{Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent},
  title =	{{Practical Computation of Graph VC-Dimension}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8},
  URN =		{urn:nbn:de:0030-drops-203731},
  doi =		{10.4230/LIPIcs.SEA.2024.8},
  annote =	{Keywords: VC-dimension, graph, algorithm}
}
Document
Track A: Algorithms, Complexity and Games
The Discrepancy of Shortest Paths

Authors: Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)


Abstract
The hereditary discrepancy of a set system is a quantitative measure of the pseudorandom properties of the system. Roughly speaking, hereditary discrepancy measures how well one can 2-color the elements of the system so that each set contains approximately the same number of elements of each color. Hereditary discrepancy has numerous applications in computational geometry, communication complexity and derandomization. More recently, the hereditary discrepancy of the set system of shortest paths has found applications in differential privacy [Chen et al. SODA 23]. The contribution of this paper is to improve the upper and lower bounds on the hereditary discrepancy of set systems of unique shortest paths in graphs. In particular, we show that any system of unique shortest paths in an undirected weighted graph has hereditary discrepancy O(n^{1/4}), and we construct lower bound examples demonstrating that this bound is tight up to polylog n factors. Our lower bounds hold even for planar graphs and bipartite graphs, and improve a previous lower bound of Ω(n^{1/6}) obtained by applying the trace bound of Chazelle and Lvov [SoCG'00] to a classical point-line system of Erdős. As applications, we improve the lower bound on the additive error for differentially-private all pairs shortest distances from Ω(n^{1/6}) [Chen et al. SODA 23] to Ω̃(n^{1/4}), and we improve the lower bound on additive error for the differentially-private all sets range queries problem to Ω̃(n^{1/4}), which is tight up to polylog n factors [Deng et al. WADS 23].

Cite as

Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27,
  author =	{Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen},
  title =	{{The Discrepancy of Shortest Paths}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.27},
  URN =		{urn:nbn:de:0030-drops-201705},
  doi =		{10.4230/LIPIcs.ICALP.2024.27},
  annote =	{Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy}
}
Document
A Connectivity-Sensitive Approach to Consensus Dynamics

Authors: Bernard Chazelle and Kritkorn Karntikoon

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)


Abstract
The paper resolves a long-standing open question in network dynamics. Averaging-based consensus has long been known to exhibit an exponential gap in relaxation time between the connected and disconnected cases, but a satisfactory explanation has remained elusive. We provide one by deriving nearly tight bounds on the s-energy of disconnected systems. This in turn allows us to relate the convergence rate of consensus dynamics to the number of connected components. We apply our results to opinion formation in social networks and provide a theoretical validation of the concept of an Overton window as an attracting manifold of "viable" opinions.

Cite as

Bernard Chazelle and Kritkorn Karntikoon. A Connectivity-Sensitive Approach to Consensus Dynamics. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{chazelle_et_al:LIPIcs.SAND.2023.10,
  author =	{Chazelle, Bernard and Karntikoon, Kritkorn},
  title =	{{A Connectivity-Sensitive Approach to Consensus Dynamics}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.10},
  URN =		{urn:nbn:de:0030-drops-179464},
  doi =		{10.4230/LIPIcs.SAND.2023.10},
  annote =	{Keywords: s-energy, dynamic networks, relaxation time, multiagent systems}
}
Document
Complexity of Linear Operators

Authors: Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, and Vladimir Podolskii

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
Let A in {0,1}^{n x n} be a matrix with z zeroes and u ones and x be an n-dimensional vector of formal variables over a semigroup (S, o). How many semigroup operations are required to compute the linear operator Ax? As we observe in this paper, this problem contains as a special case the well-known range queries problem and has a rich variety of applications in such areas as graph algorithms, functional programming, circuit complexity, and others. It is easy to compute Ax using O(u) semigroup operations. The main question studied in this paper is: can Ax be computed using O(z) semigroup operations? We prove that in general this is not possible: there exists a matrix A in {0,1}^{n x n} with exactly two zeroes in every row (hence z=2n) whose complexity is Theta(n alpha(n)) where alpha(n) is the inverse Ackermann function. However, for the case when the semigroup is commutative, we give a constructive proof of an O(z) upper bound. This implies that in commutative settings, complements of sparse matrices can be processed as efficiently as sparse matrices (though the corresponding algorithms are more involved). Note that this covers the cases of Boolean and tropical semirings that have numerous applications, e.g., in graph theory. As a simple application of the presented linear-size construction, we show how to multiply two n x n matrices over an arbitrary semiring in O(n^2) time if one of these matrices is a 0/1-matrix with O(n) zeroes (i.e., a complement of a sparse matrix).

Cite as

Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, and Vladimir Podolskii. Complexity of Linear Operators. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kulikov_et_al:LIPIcs.ISAAC.2019.17,
  author =	{Kulikov, Alexander S. and Mikhailin, Ivan and Mokhov, Andrey and Podolskii, Vladimir},
  title =	{{Complexity of Linear Operators}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.17},
  URN =		{urn:nbn:de:0030-drops-115137},
  doi =		{10.4230/LIPIcs.ISAAC.2019.17},
  annote =	{Keywords: algorithms, linear operators, commutativity, range queries, circuit complexity, lower bounds, upper bounds}
}
Document
A New Lower Bound for Semigroup Orthogonal Range Searching

Authors: Peyman Afshani

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)


Abstract
We report the first improvement in the space-time trade-off of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle’s result from 1990. This is one of the very fundamental problems in range searching with a long history. Previously, Andrew Yao’s influential result had shown that the problem is already non-trivial in one dimension [Yao, 1982]: using m units of space, the query time Q(n) must be Omega(alpha(m,n) + n/(m-n+1)) where alpha(*,*) is the inverse Ackermann’s function, a very slowly growing function. In d dimensions, Bernard Chazelle [Chazelle, 1990] proved that the query time must be Q(n) = Omega((log_beta n)^{d-1}) where beta = 2m/n. Chazelle’s lower bound is known to be tight for when space consumption is "high" i.e., m = Omega(n log^{d+epsilon}n). We have two main results. The first is a lower bound that shows Chazelle’s lower bound was not tight for "low space": we prove that we must have m Q(n) = Omega(n (log n log log n)^{d-1}). Our lower bound does not close the gap to the existing data structures, however, our second result is that our analysis is tight. Thus, we believe the gap is in fact natural since lower bounds are proven for idempotent semigroups while the data structures are built for general semigroups and thus they cannot assume (and use) the properties of an idempotent semigroup. As a result, we believe to close the gap one must study lower bounds for non-idempotent semigroups or building data structures for idempotent semigroups. We develope significantly new ideas for both of our results that could be useful in pursuing either of these directions.

Cite as

Peyman Afshani. A New Lower Bound for Semigroup Orthogonal Range Searching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{afshani:LIPIcs.SoCG.2019.3,
  author =	{Afshani, Peyman},
  title =	{{A New Lower Bound for Semigroup Orthogonal Range Searching}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.3},
  URN =		{urn:nbn:de:0030-drops-104075},
  doi =		{10.4230/LIPIcs.SoCG.2019.3},
  annote =	{Keywords: Data Structures, Range Searching, Lower bounds}
}
Document
Toward a Theory of Markov Influence Systems and their Renormalization

Authors: Bernard Chazelle

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)


Abstract
Nonlinear Markov chains are probabilistic models commonly used in physics, biology, and the social sciences. In "Markov influence systems" (MIS), the transition probabilities of the chains change as a function of the current state distribution. This work introduces a renormalization framework for analyzing the dynamics of MIS. It comes in two independent parts: first, we generalize the standard classification of Markov chain states to the dynamic case by showing how to "parse" graph sequences. We then use this framework to carry out the bifurcation analysis of a few important MIS families. In particular, we show that irreducible MIS are almost always asymptotically periodic. We also give an example of "hyper-torpid" mixing, where a stationary distribution is reached in super-exponential time, a timescale that cannot be achieved by any Markov chain.

Cite as

Bernard Chazelle. Toward a Theory of Markov Influence Systems and their Renormalization. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 58:1-58:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chazelle:LIPIcs.ITCS.2018.58,
  author =	{Chazelle, Bernard},
  title =	{{Toward a Theory of Markov Influence Systems and their Renormalization}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{58:1--58:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.58},
  URN =		{urn:nbn:de:0030-drops-83317},
  doi =		{10.4230/LIPIcs.ITCS.2018.58},
  annote =	{Keywords: Markov influence systems, nonlinear Markov chains, dynamical systems, renormalization, graph sequence parsing}
}
Document
Self-Sustaining Iterated Learning

Authors: Bernard Chazelle and Chu Wang

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)


Abstract
An important result from psycholinguistics (Griffiths & Kalish, 2005) states that no language can be learned iteratively by rational agents in a self-sustaining manner. We show how to modify the learning process slightly in order to achieve self-sustainability. Our work is in two parts. First, we characterize iterated learnability in geometric terms and show how a slight, steady increase in the lengths of the training sessions ensures self-sustainability for any discrete language class. In the second part, we tackle the nondiscrete case and investigate self-sustainability for iterated linear regression. We discuss the implications of our findings to issues of non-equilibrium dynamics in natural algorithms.

Cite as

Bernard Chazelle and Chu Wang. Self-Sustaining Iterated Learning. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{chazelle_et_al:LIPIcs.ITCS.2017.17,
  author =	{Chazelle, Bernard and Wang, Chu},
  title =	{{Self-Sustaining Iterated Learning}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.17},
  URN =		{urn:nbn:de:0030-drops-81711},
  doi =		{10.4230/LIPIcs.ITCS.2017.17},
  annote =	{Keywords: Iterated learning, language evolution, iterated Bayesian linear regression, non-equilibrium dynamics}
}
Document
Sublinear Geometric Algorithms

Authors: Bernard Chazelle, Ding Liu, and Avner Magen

Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)


Abstract
We present sublinear algorithms to such problems as Detecting of Polytope intersection, Shortest Path on 3D convex Polytopes and volume approximation.

Cite as

Bernard Chazelle, Ding Liu, and Avner Magen. Sublinear Geometric Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{chazelle_et_al:DagSemProc.05291.4,
  author =	{Chazelle, Bernard and Liu, Ding and Magen, Avner},
  title =	{{Sublinear Geometric Algorithms}},
  booktitle =	{Sublinear Algorithms},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5291},
  editor =	{Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.4},
  URN =		{urn:nbn:de:0030-drops-5548},
  doi =		{10.4230/DagSemProc.05291.4},
  annote =	{Keywords: Sublinear algorithms, computational geometry}
}
Document
Computational Geometry (Dagstuhl Seminar 9511)

Authors: Helmut Alt, Bernard Chazelle, and Raimund Seidel

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Helmut Alt, Bernard Chazelle, and Raimund Seidel. Computational Geometry (Dagstuhl Seminar 9511). Dagstuhl Seminar Report 109, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1995)


Copy BibTex To Clipboard

@TechReport{alt_et_al:DagSemRep.109,
  author =	{Alt, Helmut and Chazelle, Bernard and Seidel, Raimund},
  title =	{{Computational Geometry (Dagstuhl Seminar 9511)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{1995},
  type = 	{Dagstuhl Seminar Report},
  number =	{109},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.109},
  URN =		{urn:nbn:de:0030-drops-149970},
  doi =		{10.4230/DagSemRep.109},
}
Document
Computational Geometry (Dagstuhl Seminar 9312)

Authors: Helmut Alt, Bernard Chazelle, and Emo Welzl

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Helmut Alt, Bernard Chazelle, and Emo Welzl. Computational Geometry (Dagstuhl Seminar 9312). Dagstuhl Seminar Report 59, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)


Copy BibTex To Clipboard

@TechReport{alt_et_al:DagSemRep.59,
  author =	{Alt, Helmut and Chazelle, Bernard and Welzl, Emo},
  title =	{{Computational Geometry (Dagstuhl Seminar 9312)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{1993},
  type = 	{Dagstuhl Seminar Report},
  number =	{59},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.59},
  URN =		{urn:nbn:de:0030-drops-149479},
  doi =		{10.4230/DagSemRep.59},
}
Document
Computational Geometry (Dagstuhl Seminar 9141)

Authors: Helmut Alt, Bernard Chazelle, and Emo Welzl

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Helmut Alt, Bernard Chazelle, and Emo Welzl. Computational Geometry (Dagstuhl Seminar 9141). Dagstuhl Seminar Report 22, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1991)


Copy BibTex To Clipboard

@TechReport{alt_et_al:DagSemRep.22,
  author =	{Alt, Helmut and Chazelle, Bernard and Welzl, Emo},
  title =	{{Computational Geometry (Dagstuhl Seminar 9141)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{1991},
  type = 	{Dagstuhl Seminar Report},
  number =	{22},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.22},
  URN =		{urn:nbn:de:0030-drops-149101},
  doi =		{10.4230/DagSemRep.22},
}
  • Refine by Author
  • 7 Chazelle, Bernard
  • 3 Alt, Helmut
  • 2 Welzl, Emo
  • 1 Afshani, Peyman
  • 1 Bodwin, Greg
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Data Structures
  • 1 Discrepancy
  • 1 Iterated learning
  • 1 Lower bounds
  • 1 Markov influence systems
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 2 2019
  • 2 2024
  • 1 1991
  • 1 1993
  • 1 1995
  • Show More...