Search Results

Documents authored by Rigi-Luperti, Niccolò

Document
DOI: 10.4230/LIPIcs.ESA.2026.8
Practical Bit Vectors Supporting Constant Time Rank and Select in Optimal Space

Authors: Florian Kurpicz, Niccolò Rigi-Luperti, and Peter Sanders

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Bit vectors with support for fast rank and select are a fundamental building block for compressed data structures. We close a gap between theory and practice by mapping a design space of promising data structures, analyzing it, and experimentally evaluating a promising region. The result are implementations of rank and select data structures for bit vectors with worst-case constant query time, leading practical performance, and a space-overhead reaching below 1 %. For difficult inputs, we are ≈ 8 times faster than the best previous implementations.
Cite as

Florian Kurpicz, Niccolò Rigi-Luperti, and Peter Sanders. Practical Bit Vectors Supporting Constant Time Rank and Select in Optimal Space. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kurpicz_et_al:LIPIcs.ESA.2026.8,
  author =	{Kurpicz, Florian and Rigi-Luperti, Niccol\`{o} and Sanders, Peter},
  title =	{{Practical Bit Vectors Supporting Constant Time Rank and Select in Optimal Space}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.8},
  URN =		{urn:nbn:de:0030-drops-271443},
  doi =		{10.4230/LIPIcs.ESA.2026.8},
  annote =	{Keywords: succinct data structures, bit vectors, rank and select}
}
Artifact
Software
DOI: 10.4230/artifacts.26961
Mallob

Authors: Dominik Schreiber, Peter Sanders, Niccolò Rigi-Luperti, and Ruben Götz

Abstract
Cite as

Dominik Schreiber, Peter Sanders, Niccolò Rigi-Luperti, Ruben Götz. Mallob (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26961,
   title = {{Mallob}}, 
   author = {Schreiber, Dominik and Sanders, Peter and Rigi-Luperti, Niccol\`{o} and G\"{o}tz, Ruben},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:63e95b4ba914b33387dbf6e31babbc7b9c3904dc;origin=https://github.com/domschrei/mallob;visit=swh:1:snp:d171a3816db9a89fb89fd452be5b629b191c908c;anchor=swh:1:rev:745c357849212f4dfc33debecac44103a83e5a52}{\texttt{swh:1:dir:63e95b4ba914b33387dbf6e31babbc7b9c3904dc}} (visited on 2026-07-16)},
   url = {https://github.com/domschrei/mallob},
   doi = {10.4230/artifacts.26961},
}
Artifact
Software
DOI: 10.4230/artifacts.24204
Supplementary material for SAT'25 publication "Streamlining Distributed SAT Solver Design"

Authors: Dominik Schreiber, Niccolò Rigi-Luperti, and Armin Biere

Abstract
Cite as

Dominik Schreiber, Niccolò Rigi-Luperti, Armin Biere. Supplementary material for SAT'25 publication "Streamlining Distributed SAT Solver Design" (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24204,
   title = {{Supplementary material for SAT'25 publication "Streamlining Distributed SAT Solver Design"}}, 
   author = {Schreiber, Dominik and Rigi-Luperti, Niccol\`{o} and Biere, Armin},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:bdecc26fc577de49d3fe853d07e4ba59e3cbe2f8;origin=https://github.com/nrilu/SAT_2025_supplement_63;visit=swh:1:snp:68b6b69da5213d061c6c7608ebac8224b257b641;anchor=swh:1:rev:f8a1918d4fb7a1f8274d91716dd1910c3e703873}{\texttt{swh:1:dir:bdecc26fc577de49d3fe853d07e4ba59e3cbe2f8}} (visited on 2025-08-07)},
   url = {https://github.com/nrilu/SAT_2025_supplement_63},
   doi = {10.4230/artifacts.24204},
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.27
Streamlining Distributed SAT Solver Design

Authors: Dominik Schreiber, Niccolò Rigi-Luperti, and Armin Biere

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Distributed clause-sharing SAT solvers have recently been established as powerful automated reasoning tools that can conquer previously infeasible instances. A common design of distributed SAT solvers is to run many off-the-shelf sequential solvers in parallel, employ some diversification (e.g., restart intervals or decision orders), and share conflict clauses among the solver threads. This approach, naïvely, adopts all best practices of sequential solver design for distributed solving, where these practices may be less useful or even actively detrimental. In this work we diagnose such shortcomings in the state-of-the-art system MallobSat and propose first effective mitigations. In particular, we replace the redundant pre- and inprocessing at all threads with single-core preprocessing that runs next to the parallel search, remove LBD values from the clause-sharing operation, and slim down solver diversification to very few lightweight and uniform methods. Experimental evaluations on up to 3072 cores (64 nodes) confirm that our measures improve performance while also drastically simplifying the SAT solving program that is run in parallel.
Cite as

Dominik Schreiber, Niccolò Rigi-Luperti, and Armin Biere. Streamlining Distributed SAT Solver Design. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 27:1-27:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schreiber_et_al:LIPIcs.SAT.2025.27,
  author =	{Schreiber, Dominik and Rigi-Luperti, Niccol\`{o} and Biere, Armin},
  title =	{{Streamlining Distributed SAT Solver Design}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{27:1--27:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.27},
  URN =		{urn:nbn:de:0030-drops-237615},
  doi =		{10.4230/LIPIcs.SAT.2025.27},
  annote =	{Keywords: Satisfiability, parallel SAT solving, distributed computing, preprocessing}
}

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