2 Search Results for "Sobel, Joshua"

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.65
Brief Announcement: Congested Clique Counting for Local Gibbs Distributions

Authors: Joshua Z. Sobel

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
There are well established reductions between combinatorial sampling and counting problems (Jerrum, Valiant, Vazirani TCS 1986). Building off of a very recent parallel algorithm utilizing this connection (Liu, Yin, Zhang arxiv 2024), we demonstrate the first approximate counting algorithm in the CongestedClique for a wide range of problems. Most interestingly, we present an algorithm for approximating the number of q-colorings of a graph within ε-multiplicative error, when q > αΔ for any constant α > 2, in Õ((n^{1/3})/ε²) rounds. More generally, we achieve a runtime of Õ((n^{1/3})/ε²) rounds for approximating the partition function of Gibbs distributions defined over graphs when simple locality and fast mixing conditions hold. Gibbs distributions are widely used in fields such as machine learning and statistical physics. We obtain our result by providing an algorithm to draw n random samples from a distributed Markov chain in parallel, using similar ideas to triangle counting (Dolev, Lenzen, Peled DISC 2012) and semiring matrix multiplication (Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela PODC 2015). Aside from counting problems, this result may be interesting for other applications requiring a large number of samples.
Cite as

Joshua Z. Sobel. Brief Announcement: Congested Clique Counting for Local Gibbs Distributions. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 65:1-65:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sobel:LIPIcs.DISC.2025.65,
  author =	{Sobel, Joshua Z.},
  title =	{{Brief Announcement: Congested Clique Counting for Local Gibbs Distributions}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{65:1--65:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.65},
  URN =		{urn:nbn:de:0030-drops-248811},
  doi =		{10.4230/LIPIcs.DISC.2025.65},
  annote =	{Keywords: Distributed Sampling, Approximate Counting, Markov Chains, Gibbs Distributions}
}
Document
DOI: 10.4230/LIPIcs.CPM.2021.24
AWLCO: All-Window Length Co-Occurrence

Authors: Joshua Sobel, Noah Bertram, Chen Ding, Fatemeh Nargesian, and Daniel Gildea

Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)

Abstract
Analyzing patterns in a sequence of events has applications in text analysis, computer programming, and genomics research. In this paper, we consider the all-window-length analysis model which analyzes a sequence of events with respect to windows of all lengths. We study the exact co-occurrence counting problem for the all-window-length analysis model. Our first algorithm is an offline algorithm that counts all-window-length co-occurrences by performing multiple passes over a sequence and computing single-window-length co-occurrences. This algorithm has the time complexity O(n) for each window length and thus a total complexity of O(n²) and the space complexity O(|I|) for a sequence of size n and an itemset of size |I|. We propose AWLCO, an online algorithm that computes all-window-length co-occurrences in a single pass with the time complexity of O(n) and space complexity of O(√{n|I|}), assuming perfect hashing. Following this, we generalize our use case to patterns in which we propose an algorithm that computes all-window-length co-occurrence with time complexity O(n|I|), assuming perfect hashing, with an additional pre-processing step and space complexity O(√{n|I|}+|I|), plus the overhead of the Aho-Corasick algorithm [Aho and Corasick, 1975].
Cite as

Joshua Sobel, Noah Bertram, Chen Ding, Fatemeh Nargesian, and Daniel Gildea. AWLCO: All-Window Length Co-Occurrence. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sobel_et_al:LIPIcs.CPM.2021.24,
  author =	{Sobel, Joshua and Bertram, Noah and Ding, Chen and Nargesian, Fatemeh and Gildea, Daniel},
  title =	{{AWLCO: All-Window Length Co-Occurrence}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{24:1--24:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.24},
  URN =		{urn:nbn:de:0030-drops-139759},
  doi =		{10.4230/LIPIcs.CPM.2021.24},
  annote =	{Keywords: Itemsets, Data Sequences, Co-occurrence}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2021

  • Refine by Author
  • 1 Bertram, Noah
  • 1 Ding, Chen
  • 1 Gildea, Daniel
  • 1 Nargesian, Fatemeh
  • 1 Sobel, Joshua
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Random walks and Markov chains
  • 1 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 1 Approximate Counting
  • 1 Co-occurrence
  • 1 Data Sequences
  • 1 Distributed Sampling
  • 1 Gibbs Distributions
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact