6 Search Results for "Vu, Van"

Document
DOI: 10.4230/LIPIcs.AofA.2024.11
Tree Walks and the Spectrum of Random Graphs

Authors: Eva-Maria Hainzl and Élie de Panafieu

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

Abstract
It is a classic result in spectral theory that the limit distribution of the spectral measure of random graphs G(n,p) converges to the semicircle law in case np tends to infinity with n. The spectral measure for random graphs G(n,c/n) however is less understood. In this work, we combine and extend two combinatorial approaches by Bauer and Golinelli (2001) and Enriquez and Menard (2016) and approximate the moments of the spectral measure by counting walks that span trees.
Cite as

Eva-Maria Hainzl and Élie de Panafieu. Tree Walks and the Spectrum of Random Graphs. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hainzl_et_al:LIPIcs.AofA.2024.11,
  author =	{Hainzl, Eva-Maria and de Panafieu, \'{E}lie},
  title =	{{Tree Walks and the Spectrum of Random Graphs}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.11},
  URN =		{urn:nbn:de:0030-drops-204466},
  doi =		{10.4230/LIPIcs.AofA.2024.11},
  annote =	{Keywords: Spectrum of random matrices, generating functions}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.7
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy

Authors: Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
The following question arises naturally in the study of graph streaming algorithms: Is there any graph problem which is "not too hard", in that it can be solved efficiently with total communication (nearly) linear in the number n of vertices, and for which, nonetheless, any streaming algorithm with Õ(n) space (i.e., a semi-streaming algorithm) needs a polynomial n^Ω(1) number of passes? Assadi, Chen, and Khanna [STOC 2019] were the first to prove that this is indeed the case. However, the lower bounds that they obtained are for rather non-standard graph problems. Our first main contribution is to present the first polynomial-pass lower bounds for natural "not too hard" graph problems studied previously in the streaming model: k-cores and degeneracy. We devise a novel communication protocol for both problems with near-linear communication, thus showing that k-cores and degeneracy are natural examples of "not too hard" problems. Indeed, previous work have developed single-pass semi-streaming algorithms for approximating these problems. In contrast, we prove that any semi-streaming algorithm for exactly solving these problems requires (almost) Ω(n^{1/3}) passes. The lower bound follows by a reduction from a generalization of the hidden pointer chasing (HPC) problem of Assadi, Chen, and Khanna, which is also the basis of their earlier semi-streaming lower bounds. Our second main contribution is improved round-communication lower bounds for the underlying communication problems at the basis of these reductions: - We improve the previous lower bound of Assadi, Chen, and Khanna for HPC to achieve optimal bounds for this problem. - We further observe that all current reductions from HPC can also work with a generalized version of this problem that we call MultiHPC, and prove an even stronger and optimal lower bound for this generalization. These two results collectively allow us to improve the resulting pass lower bounds for semi-streaming algorithms by a polynomial factor, namely, from n^{1/5} to n^{1/3} passes.
Cite as

Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7,
  author =	{Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik},
  title =	{{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.7},
  URN =		{urn:nbn:de:0030-drops-204035},
  doi =		{10.4230/LIPIcs.CCC.2024.7},
  annote =	{Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.10
The Bit Complexity of Dynamic Algebraic Formulas and Their Determinants

Authors: Emile Anand, Jan van den Brand, Mehrdad Ghadiri, and Daniel J. Zhang

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

Abstract
Many iterative algorithms in computer science require repeated computation of some algebraic expression whose input varies slightly from one iteration to the next. Although efficient data structures have been proposed for maintaining the solution of such algebraic expressions under low-rank updates, most of these results are only analyzed under exact arithmetic (real-RAM model and finite fields) which may not accurately reflect the more limited complexity guarantees of real computers. In this paper, we analyze the stability and bit complexity of such data structures for expressions that involve the inversion, multiplication, addition, and subtraction of matrices under the word-RAM model. We show that the bit complexity only increases linearly in the number of matrix operations in the expression. In addition, we consider the bit complexity of maintaining the determinant of a matrix expression. We show that the required bit complexity depends on the logarithm of the condition number of matrices instead of the logarithm of their determinant. Finally, we discuss rank maintenance and its connections to determinant maintenance. Our results have wide applications ranging from computational geometry (e.g., computing the volume of a polytope) to optimization (e.g., solving linear programs using the simplex algorithm).
Cite as

Emile Anand, Jan van den Brand, Mehrdad Ghadiri, and Daniel J. Zhang. The Bit Complexity of Dynamic Algebraic Formulas and Their Determinants. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.ICALP.2024.10,
  author =	{Anand, Emile and van den Brand, Jan and Ghadiri, Mehrdad and Zhang, Daniel J.},
  title =	{{The Bit Complexity of Dynamic Algebraic Formulas and Their Determinants}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{10:1--10: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.10},
  URN =		{urn:nbn:de:0030-drops-201538},
  doi =		{10.4230/LIPIcs.ICALP.2024.10},
  annote =	{Keywords: Data Structures, Online Algorithms, Bit Complexity}
}
Document
DOI: 10.4230/DagRep.12.6.112
Human-Centered Artificial Intelligence (Dagstuhl Seminar 22262)

Authors: Wendy E. Mackay, John Shawe-Taylor, and Frank van Harmelen

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

Abstract
This report documents the program and the outcomes of Dagstuhl Perspectives Workshop 22262 "Human-Centered Artificial Intelligence". The goal of this Dagstuhl Perspectives Workshops is to provide the scientific and technological foundations for designing and deploying hybrid human-centered AI systems that work in partnership with human beings and that enhance human capabilities rather than replace human intelligence. Fundamentally new solutions are needed for core research problems in AI and human-computer interaction (HCI), especially to help people understand actions recommended or performed by AI systems and to facilitate meaningful interaction between humans and AI systems. Specific challenges include: learning complex world models; building effective and explainable machine learning systems; developing human-controllable intelligent systems; adapting AI systems to dynamic, open-ended real-world environments (in particular robots and autonomous systems); achieving in-depth understanding of humans and complex social contexts; and enabling self-reflection within AI systems.
Cite as

Wendy E. Mackay, John Shawe-Taylor, and Frank van Harmelen. Human-Centered Artificial Intelligence (Dagstuhl Seminar 22262). In Dagstuhl Reports, Volume 12, Issue 6, pp. 112-117, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{mackay_et_al:DagRep.12.6.112,
  author =	{Mackay, Wendy E. and Shawe-Taylor, John and van Harmelen, Frank},
  title =	{{Human-Centered Artificial Intelligence (Dagstuhl Seminar 22262)}},
  pages =	{112--117},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{6},
  editor =	{Mackay, Wendy E. and Shawe-Taylor, John and van Harmelen, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.6.112},
  URN =		{urn:nbn:de:0030-drops-174579},
  doi =		{10.4230/DagRep.12.6.112},
  annote =	{Keywords: Human-centered Artificial Intelligence, Human-Computer Interaction, Hybrid Intelligence}
}
Document
DOI: 10.4230/DagRep.11.8.11
Structure and Learning (Dagstuhl Seminar 21362)

Authors: Tiansi Dong, Achim Rettinger, Jie Tang, Barbara Tversky, and Frank van Harmelen

Published in: Dagstuhl Reports, Volume 11, Issue 8 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21362 "Structure and Learning", held from September 5 to 10, 2021. Structure and learning are among the most prominent topics in Artificial Intelligence (AI) today. Integrating symbolic and numeric inference was set as one of the next open AI problems at the Townhall meeting "A 20 Year Roadmap for AI" at AAAI 2019. In this Dagstuhl seminar, we discussed related problems from an interdiscplinary perspective, in particular, Cognitive Science, Cognitive Psychology, Physics, Computational Humor, Linguistic, Machine Learning, and AI. This report overviews presentations and working groups during the seminar, and lists two open problems.
Cite as

Tiansi Dong, Achim Rettinger, Jie Tang, Barbara Tversky, and Frank van Harmelen. Structure and Learning (Dagstuhl Seminar 21362). In Dagstuhl Reports, Volume 11, Issue 8, pp. 11-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{dong_et_al:DagRep.11.8.11,
  author =	{Dong, Tiansi and Rettinger, Achim and Tang, Jie and Tversky, Barbara and van Harmelen, Frank},
  title =	{{Structure and Learning (Dagstuhl Seminar 21362)}},
  pages =	{11--34},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{11},
  number =	{8},
  editor =	{Dong, Tiansi and Rettinger, Achim and Tang, Jie and Tversky, Barbara and van Harmelen, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.8.11},
  URN =		{urn:nbn:de:0030-drops-157670},
  doi =		{10.4230/DagRep.11.8.11},
  annote =	{Keywords: Knowledge graph, Machine learning, Neural-symbol unification}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.20
Reaching a Consensus on Random Networks: The Power of Few

Authors: Linh Tran and Van Vu

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
A community of n individuals splits into two camps, Red and Blue. The individuals are connected by a social network, which influences their colors. Everyday, each person changes his/her color according to the majority of his/her neighbors. Red (Blue) wins if everyone in the community becomes Red (Blue) at some point. We study this process when the underlying network is the random Erdos-Renyi graph G(n, p). With a balanced initial state (n/2 persons in each camp), it is clear that each color wins with the same probability. Our study reveals that for any constants p and ε, there is a constant c such that if one camp has n/2 + c individuals at the initial state, then it wins with probability at least 1 - ε. The surprising fact here is that c does not depend on n, the population of the community. When p = 1/2 and ε = .1, one can set c = 6, meaning one camp has n/2 + 6 members initially. In other words, it takes only 6 extra people to win an election with overwhelming odds. We also generalize the result to p = p_n = o(1) in a separate paper.
Cite as

Linh Tran and Van Vu. Reaching a Consensus on Random Networks: The Power of Few. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{tran_et_al:LIPIcs.APPROX/RANDOM.2020.20,
  author =	{Tran, Linh and Vu, Van},
  title =	{{Reaching a Consensus on Random Networks: The Power of Few}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.20},
  URN =		{urn:nbn:de:0030-drops-126239},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.20},
  annote =	{Keywords: Random Graphs Majority Dynamics Consensus}
}
  • Refine by Author
  • 2 van Harmelen, Frank
  • 1 Anand, Emile
  • 1 Assadi, Sepehr
  • 1 Dong, Tiansi
  • 1 Ghadiri, Mehrdad
  • Show More...

  • Refine by Classification
  • 2 Computing methodologies → Artificial intelligence
  • 2 Computing methodologies → Machine learning
  • 2 Mathematics of computing → Probability and statistics
  • 1 Computing methodologies → Symbolic and algebraic manipulation
  • 1 Human-centered computing → Human computer interaction (HCI)
  • Show More...

  • Refine by Keyword
  • 1 Bit Complexity
  • 1 Communication complexity
  • 1 Data Structures
  • 1 Graph streaming
  • 1 Human-Computer Interaction
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2024
  • 1 2020
  • 1 2022
  • 1 2023

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact