DROPS

Document

A Survey of Real-Time Support, Analysis, and Advancements in ROS 2

Authors: Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper

Published in: LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1

Abstract

The Robot Operating System 2 (ROS 2) has emerged as a relevant middleware framework for robotic applications, offering modularity, distributed execution, and communication. In the last six years, ROS 2 has drawn increasing attention from the real-time systems community and industry. This survey presents a comprehensive overview of research efforts that analyze, enhance, and extend ROS 2 to support real-time execution. We first provide a detailed description of the internal scheduling mechanisms of ROS 2 and its layered architecture, including the interaction with DDS-based communication and other communication middleware. We then review key contributions from the literature, covering timing analysis for both single- and multi-threaded executors, metrics such as response time, reaction time, and data age, and different communication modes. The survey also discusses community-driven enhancements to the ROS 2 runtime, including new executor algorithm designs, real-time GPU management, and microcontroller support via micro-ROS. Furthermore, we summarize techniques for bounding DDS communication delays, message filters, and profiling tools that have been developed to support analysis and experimentation. To help systematize this growing body of work, we introduce taxonomies that classify the surveyed contributions based on different criteria. This survey aims to guide both researchers and practitioners in understanding and improving the real-time capabilities of ROS 2.

Cite as

Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper. A Survey of Real-Time Support, Analysis, and Advancements in ROS 2. In LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1, pp. 1:1-1:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{casini_et_al:LITES.11.1.1,
  author =	{Casini, Daniel and Chen, Jian-Jia and Li, Jing and Reghenzani, Federico and Teper, Harun},
  title =	{{A Survey of Real-Time Support, Analysis, and Advancements in ROS 2}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:37},
  ISSN =	{2199-2002},
  year =	{2026},
  volume =	{11},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.11.1.1},
  URN =		{urn:nbn:de:0030-drops-257914},
  doi =		{10.4230/LITES.11.1.1},
  annote =	{Keywords: ROS 2, middleware, real-time, timing predictability, publish-subscribe}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.23

Simple Circuit Extensions for XOR in PTIME

Authors: Marco Carmosino, Ngu Dang, and Tim Jackman

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

The Minimum Circuit Size Problem for Partial Functions (MCSP^*) is hard assuming the Exponential Time Hypothesis (ETH) (Ilango, 2020). This breakthrough result leveraged a characterization of the optimal {∧, ∨, ¬} circuits for n-bit OR (OR_n) and a reduction from the partial f-Simple Extension Problem where f = OR_n. It remains open to extend that reduction to show ETH-hardness of total MCSP. However, Ilango observed that the total f-Simple Extension Problem is easy whenever f is computed by read-once formulas (like OR_n). Therefore, extending Ilango’s proof to total MCSP would require replacing OR_n with a more complex but similarly well-understood Boolean function. This work shows that the f-Simple Extension problem remains easy when f is the next natural candidate: XOR_n. We first develop a fixed-parameter tractable algorithm for the f-Simple Extension Problem that is efficient whenever the optimal circuits for f are (1) linear in size, (2) polynomially "few" and efficiently enumerable in the truth-table size (up to isomorphism and permutation of inputs), and (3) all have constant bounded fan-out. XOR_n satisfies all three of these conditions. When ¬ gates count towards circuit size, optimal XOR_n circuits are binary trees of n-1 subcircuits computing (¬)XOR₂ (Kombarov, 2011). We extend this characterization when ¬ gates do not contribute the circuit size. Thus, the XOR-Simple Extension Problem is in polynomial time under both measures of circuit complexity. We conclude by discussing conjectures about the complexity of the f-Simple Extension problem for each explicit function f with known and unrestricted circuit lower bounds over the DeMorgan basis. Examining the conditions under which our Simple Extension Solver is efficient, we argue that multiplexer functions (MUX) are the most promising candidate for ETH-hardness of a Simple Extension Problem, towards proving ETH-hardness of total MCSP.

Cite as

Marco Carmosino, Ngu Dang, and Tim Jackman. Simple Circuit Extensions for XOR in PTIME. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{carmosino_et_al:LIPIcs.STACS.2026.23,
  author =	{Carmosino, Marco and Dang, Ngu and Jackman, Tim},
  title =	{{Simple Circuit Extensions for XOR in PTIME}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{23:1--23:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.23},
  URN =		{urn:nbn:de:0030-drops-255127},
  doi =		{10.4230/LIPIcs.STACS.2026.23},
  annote =	{Keywords: Minimum Circuit Size Problem, Circuit Lower Bounds, Exponential Time Hypothesis}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.62

Relative Compressed Reverse Suffix Array

Authors: Muhammed Oguzhan Kulekci, Mano Prakash Parthasarathi, Rahul Shah, and Sharma V. Thankachan

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

Suffix trees and suffix arrays are two fundamental data structures in the field of string algorithms. For a string (a.k.a. text or sequence) of length n over an alphabet of size σ, these structures typically require O(nlog n) bits of space. The FM-index provides a compressed representation of the suffix array in ≈ nlog σ bits, allowing for efficient queries on both the suffix array and its inverse array in near logarithmic time. In certain applications, such as approximate pattern matching (i.e., with wildcards, mismatches, edits), there is a need to access the suffix array of a text, as well as the suffix array of text’s reverse. Motivated by this, we explore the possibility of encoding the suffix array of the reversed text in a compact form, assuming the availability of the FM-index for the original text. Our first solution is an O(n)-bit (relative) encoding of the suffix array of the reversed text, with the time for decoding an entry being only O(log^*n) times that of decoding an entry in the text’s suffix array using FM-index. We then demonstrate how to reduce the space to O(n/κ) bits for a parameter κ, while multiplicative factor in time becomes approximately O(κlog^*n+κ³). We can also support inverse suffix array and longest common extension queries on the reversed text. These results are achieved through some careful and non-trivial application of various succinct data structure techniques.

Cite as

Muhammed Oguzhan Kulekci, Mano Prakash Parthasarathi, Rahul Shah, and Sharma V. Thankachan. Relative Compressed Reverse Suffix Array. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 62:1-62:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kulekci_et_al:LIPIcs.STACS.2026.62,
  author =	{Kulekci, Muhammed Oguzhan and Parthasarathi, Mano Prakash and Shah, Rahul and Thankachan, Sharma V.},
  title =	{{Relative Compressed Reverse Suffix Array}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{62:1--62:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.62},
  URN =		{urn:nbn:de:0030-drops-255512},
  doi =		{10.4230/LIPIcs.STACS.2026.62},
  annote =	{Keywords: String Matching, Text Indexing, Data Structures, Suffix Trees}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.49

Debordering Closure Results in Determinantal and Pfaffian Ideals

Authors: Anakin Dey and Zeyu Guo

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

One important question in algebraic complexity is understanding the complexity of polynomial ideals (Grochow, Bulletin of EATCS 131, 2020). Andrews and Forbes (STOC 2022) studied the determinantal ideals I^{det}_{n,m,r} generated by the r× r minors of n× m matrices. Over fields of characteristic zero or of sufficiently large characteristic, they showed that for any nonzero f ∈ I^{det}_{n,m,r}, the determinant of a t × t matrix of variables with t = Θ{r^{1/3}} is approximately computed by a constant-depth, polynomial-size f-oracle algebraic circuit, in the sense that the determinant lies in the border of such circuits. An analogous result was also obtained for Pfaffians in the same paper. In this work, we deborder the result of Andrews and Forbes by showing that when f has polynomial degree, the determinant is in fact exactly computed by a constant-depth, polynomial-size f-oracle algebraic circuit. We further establish an analogous result for Pfaffian ideals. Our results are established using the isolation lemma, combined with a careful analysis of straightening-law expansions of polynomials in determinantal and Pfaffian ideals.

Cite as

Anakin Dey and Zeyu Guo. Debordering Closure Results in Determinantal and Pfaffian Ideals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ITCS.2026.49,
  author =	{Dey, Anakin and Guo, Zeyu},
  title =	{{Debordering Closure Results in Determinantal and Pfaffian Ideals}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.49},
  URN =		{urn:nbn:de:0030-drops-253363},
  doi =		{10.4230/LIPIcs.ITCS.2026.49},
  annote =	{Keywords: Algebraic circuit complexity, Isolation lemma, Debordering}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.4

Pseudodeterministic Algorithms for Minimum Cut Problems

Authors: Aryan Agarwala and Nithin Varma

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

In this paper we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024). Furthermore, we implement our algorithm in streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known.

Cite as

Aryan Agarwala and Nithin Varma. Pseudodeterministic Algorithms for Minimum Cut Problems. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.4,
  author =	{Agarwala, Aryan and Varma, Nithin},
  title =	{{Pseudodeterministic Algorithms for Minimum Cut Problems}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.4},
  URN =		{urn:nbn:de:0030-drops-252917},
  doi =		{10.4230/LIPIcs.ITCS.2026.4},
  annote =	{Keywords: Minimum Cut, Pseudodeterministic Algorithms}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.56

The Hardness of Learning Quantum Circuits and Its Cryptographic Applications

Authors: Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to {NISQ-friendly quantum cryptography}. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against {noiseless} quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.

Cite as

Bill Fefferman, Soumik Ghosh, Makrand Sinha, and Henry Yuen. The Hardness of Learning Quantum Circuits and Its Cryptographic Applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 56:1-56:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fefferman_et_al:LIPIcs.ITCS.2026.56,
  author =	{Fefferman, Bill and Ghosh, Soumik and Sinha, Makrand and Yuen, Henry},
  title =	{{The Hardness of Learning Quantum Circuits and Its Cryptographic Applications}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{56:1--56:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.56},
  URN =		{urn:nbn:de:0030-drops-253431},
  doi =		{10.4230/LIPIcs.ITCS.2026.56},
  annote =	{Keywords: quantum learning, quantum circuits, cryptographic hardness, one-way state generators}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.60

Total Search Problems in ZPP

Authors: Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, and Weiqiang Yuan

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas. While TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class assuming that NP is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions. Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP∩ TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code: - We define a problem called Empty-Child capturing finding a leaf in a rooted (binary) tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with "heights" is complete for the intersection of SOPL and Lossy-Code. - We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. Somewhat surprisingly, we show the resulting new problems are still reducible to Lossy-Code. A technical highlight of this result is that they are proved by formalizations in bounded arithmetic, specifically in Jeřábek’s theory APC₁ (JSL 2007). - Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code.

Cite as

Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, and Weiqiang Yuan. Total Search Problems in ZPP. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 60:1-60:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fleming_et_al:LIPIcs.ITCS.2026.60,
  author =	{Fleming, Noah and Grosser, Stefan and Jain, Siddhartha and Li, Jiawei and Ren, Hanlin and Shirley, Morgan and Yuan, Weiqiang},
  title =	{{Total Search Problems in ZPP}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{60:1--60:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.60},
  URN =		{urn:nbn:de:0030-drops-253473},
  doi =		{10.4230/LIPIcs.ITCS.2026.60},
  annote =	{Keywords: TFNP, lossy code, randomized proof systems, query complexity}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.61

Random Unitaries in Constant (Quantum) Time

Authors: Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.

Cite as

Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. Random Unitaries in Constant (Quantum) Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 61:1-61:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{foxman_et_al:LIPIcs.ITCS.2026.61,
  author =	{Foxman, Ben and Parham, Natalie and Vasconcelos, Francisca and Yuen, Henry},
  title =	{{Random Unitaries in Constant (Quantum) Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{61:1--61:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.61},
  URN =		{urn:nbn:de:0030-drops-253481},
  doi =		{10.4230/LIPIcs.ITCS.2026.61},
  annote =	{Keywords: Quantum Information, Pseudorandomness, Circuit Complexity}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.113

Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP

Authors: Benjamin Rossman and Davidson Zhu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

The sum-of-squares (SoS) complexity of a d-multiquadratic polynomial f (quadratic in each of d blocks of n variables) is the minimum s such that f = ∑_{i = 1}^s g_i² with each g_i d-multilinear. In the case d = 2, Hrubeš, Wigderson and Yehudayoff [Hrubeš et al., 2011] showed that an n^{1+Ω(1)} lower bound on the SoS complexity of explicit biquadratic polynomials implies an exponential lower bound for non-commutative arithmetic circuits. In this paper, we establish an analogous connection between general multiquadratic sum-of-squares and commutative arithmetic formulas. Specifically, we show that an n^{d-o(log d)} lower bound on the SoS complexity of explicit d-multiquadratic polynomials, for any d = d(n) with ω(1) ≤ d(n) ≤ O((log n)/(log log n)), would separate the algebraic complexity classes VNC¹ and VNP.

Cite as

Benjamin Rossman and Davidson Zhu. Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 113:1-113:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rossman_et_al:LIPIcs.ITCS.2026.113,
  author =	{Rossman, Benjamin and Zhu, Davidson},
  title =	{{Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{113:1--113:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.113},
  URN =		{urn:nbn:de:0030-drops-254006},
  doi =		{10.4230/LIPIcs.ITCS.2026.113},
  annote =	{Keywords: sum-of-squares, arithmetic formulas}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.111

Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

Authors: Hanlin Ren, Yichuan Wang, and Yan Zhong

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Given a circuit G: {0, 1}ⁿ → {0, 1}^m with m > n, the range avoidance problem (Avoid) asks to output a string y ∈ {0, 1}^m that is not in the range of G. Besides its profound connection to circuit complexity and explicit construction problems, this problem is also related to the existence of proof complexity generators - circuits G: {0, 1}ⁿ → {0, 1}^m where m > n but for every y ∈ {0, 1}^m, it is infeasible to prove the statement "y ̸ ∈ Range(G)" in a given propositional proof system. This paper connects these two problems with the existence of demi-bits generators, a fundamental cryptographic primitive against nondeterministic adversaries introduced by Rudich (RANDOM '97). - We show that the existence of demi-bits generators implies Avoid is hard for nondeterministic algorithms. This resolves an open problem raised by Chen and Li (STOC '24). Furthermore, assuming the demi-hardness of certain LPN-style generators or Goldreich’s PRG, we prove the hardness of Avoid even when the instances are constant-degree polynomials over 𝔽₂. - We show that the dual weak pigeonhole principle is unprovable in Cook’s theory PV₁ under the existence of demi-bits generators secure against AM/_{O(1)}, thereby separating Jeřábek’s theory APC₁ from PV₁. Previously, Ilango, Li, and Williams (STOC '23) obtained the same separation under different (and arguably stronger) cryptographic assumptions. - We transform demi-bits generators to proof complexity generators that are pseudo-surjective in certain parameter regime. Pseudo-surjectivity is the strongest form of hardness considered in the literature for proof complexity generators. Our constructions are inspired by the recent breakthroughs on the hardness of Avoid by Ilango, Li, and Williams (STOC '23) and Chen and Li (STOC '24). We use randomness extractors to significantly simplify the construction and the proof.

Cite as

Hanlin Ren, Yichuan Wang, and Yan Zhong. Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 111:1-111:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ren_et_al:LIPIcs.ITCS.2026.111,
  author =	{Ren, Hanlin and Wang, Yichuan and Zhong, Yan},
  title =	{{Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{111:1--111:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.111},
  URN =		{urn:nbn:de:0030-drops-253982},
  doi =		{10.4230/LIPIcs.ITCS.2026.111},
  annote =	{Keywords: Range Avoidance, Proof Complexity Generators}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.17

Unconditional Quantum Advantage for Sampling with Shallow Circuits

Authors: Adam Bene Watts and Natalie Parham

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit with bounded fan-in cannot. They also pose the question: Can we achieve a similar proof of separation for an input-independent sampling task? In this paper, we show that the answer to this question is yes when the number of random input bits given to the classical circuit is bounded. We introduce a distribution D_{n} over {0,1}ⁿ and construct a constant-depth uniform quantum circuit family {C_n}_n such that C_n samples from a distribution close to D_{n} in total variation distance. For any δ < 1 we also prove, unconditionally, that any classical circuit with bounded fan-in gates that takes as input kn + n^δ i.i.d. Bernouli random variables with entropy 1/k and produces output close to D_{n} in total variation distance has depth Ω(log log n). This gives an unconditional proof that constant-depth quantum circuits can sample from distributions that can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out, but access to an unbounded number of i.i.d random inputs. The distribution D_n and classical circuit lower bounds are inspired by work of Viola, in which he shows a different (but related) distribution cannot be sampled from approximately by constant-depth bounded fan-in classical circuits.

Cite as

Adam Bene Watts and Natalie Parham. Unconditional Quantum Advantage for Sampling with Shallow Circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{benewatts_et_al:LIPIcs.ITCS.2026.17,
  author =	{Bene Watts, Adam and Parham, Natalie},
  title =	{{Unconditional Quantum Advantage for Sampling with Shallow Circuits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.17},
  URN =		{urn:nbn:de:0030-drops-253048},
  doi =		{10.4230/LIPIcs.ITCS.2026.17},
  annote =	{Keywords: Circuit Complexity, Sampling Separation, Shallow Quantum Circuits, Unconditional Separations, Complexity of Distributions}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.32

Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem

Authors: Jin-Yi Cai and Ben Young

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Valiant’s Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets ℱ and 𝒢 of tensors (a.k.a. constraint functions or signatures) are related by a holographic transformation, then ℱ and 𝒢 are Holant-indistinguishable, i.e., every tensor network using tensors from ℱ, respectively from 𝒢, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on vanishing signatures, those which are Holant-indistinguishable from 0. We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable ℱ and 𝒢 always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their GL_q-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class TOCI introduced by Lysikov and Walter [Vladimir Lysikov and Michael Walter, 2024], and hence hard for graph isomorphism.

Cite as

Jin-Yi Cai and Ben Young. Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ITCS.2026.32,
  author =	{Cai, Jin-Yi and Young, Ben},
  title =	{{Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.32},
  URN =		{urn:nbn:de:0030-drops-253198},
  doi =		{10.4230/LIPIcs.ITCS.2026.32},
  annote =	{Keywords: Holant, Orbit Closure Intersection, Homomorphism Indistinguishability, Tensor Network}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.37

New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String

Authors: Lijie Chen, Yang Hu, and Hanlin Ren

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

The algebrization barrier, proposed by Aaronson and Wigderson (STOC '08, ToCT '09), captures the limitations of many complexity-theoretic techniques based on arithmetization. Notably, several circuit lower bounds that overcome the relativization barrier (Buhrman-Fortnow-Thierauf, CCC '98; Vinodchandran, TCS '05; Santhanam, STOC '07, SICOMP '09) remain subject to the algebrization barrier. In this work, we establish several new algebrization barriers to circuit lower bounds by studying the communication complexity of the following problem, called XOR-Missing-String: For m < 2^{n/2}, Alice gets a list of m strings x₁, … , x_m ∈ {0, 1}ⁿ, Bob gets a list of m strings y₁, … , y_m ∈ {0, 1}ⁿ, and the goal is to output a string s ∈ {0, 1}ⁿ that is not equal to x_i⊕ y_j for any i, j ∈ [m]. 1) We construct an oracle A₁ and its multilinear extension A₁̃ such that PostBPE^{A₁̃} has linear-size A₁-oracle circuits on infinitely many input lengths. That is, proving PostBPE ̸ ⊆ i.o.- SIZE[O(n)] requires non-algebrizing techniques. This barrier follows from a PostBPP communication lower bound for XOR-Missing-String. This is in contrast to the well-known algebrizing lower bound MA_E (⊆ PostBPE) ̸ ⊆ P/_poly. 2) We construct an oracle A₂ and its multilinear extension A₂̃ such that BPE^{A₂̃} has linear-size A₂-oracle circuits on all input lengths. Previously, a similar barrier was demonstrated by Aaronson and Wigderson, but in their result, A₂̃ is only a multiquadratic extension of A₂. Our results show that communication complexity is more useful than previously thought for proving algebrization barriers, as Aaronson and Wigderson wrote that communication-based barriers were "more contrived". This serves as an example of how XOR-Missing-String forms new connections between communication lower bounds and algebrization barriers. 3) Finally, we study algebrization barriers to circuit lower bounds for MA_E. Buhrman, Fortnow, and Thierauf proved a sub-half-exponential circuit lower bound for MA_E via algebrizing techniques. Toward understanding whether the half-exponential bound can be improved, we define a natural subclass of MA_E that includes their hard MA_E language, and prove the following result: For every super-half-exponential function h(n), we construct an oracle A₃ and its multilinear extension A₃̃ such that this natural subclass of MA_E^{A₃̃} has h(n)-size A₃-oracle circuits on all input lengths. This suggests that half-exponential might be the correct barrier for MA_E circuit lower bounds w.r.t. algebrizing techniques.

Cite as

Lijie Chen, Yang Hu, and Hanlin Ren. New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2026.37,
  author =	{Chen, Lijie and Hu, Yang and Ren, Hanlin},
  title =	{{New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.37},
  URN =		{urn:nbn:de:0030-drops-253246},
  doi =		{10.4230/LIPIcs.ITCS.2026.37},
  annote =	{Keywords: circuit lower bound, algebrization barrier, missing string, communication complexity}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.112

Lower Bounds Beyond DNF of Parities

Authors: Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We consider a subclass of AC⁰[2] circuits that simultaneously captures DNF∘Xor and depth-3 AC⁰ circuits. For this class we show a technique for proving lower bounds inspired by the top-down approach. We give lower bounds for the middle slice function, inner product function, and affine dispersers.

Cite as

Artur Riazanov, Anastasia Sofronova, and Dmitry Sokolov. Lower Bounds Beyond DNF of Parities. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 112:1-112:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{riazanov_et_al:LIPIcs.ITCS.2026.112,
  author =	{Riazanov, Artur and Sofronova, Anastasia and Sokolov, Dmitry},
  title =	{{Lower Bounds Beyond DNF of Parities}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{112:1--112:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.112},
  URN =		{urn:nbn:de:0030-drops-253996},
  doi =		{10.4230/LIPIcs.ITCS.2026.112},
  annote =	{Keywords: boolean circuits, top-down, unpredictability}
}

Document

Research

DOI: 10.4230/TGDK.3.3.4

Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web

Authors: Florian Ruosch, Cristina Sarasua, and Abraham Bernstein

Published in: TGDK, Volume 3, Issue 3 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 3

Abstract

In Argument Mining, predicting argumentative relations between texts (or spans) remains one of the most challenging aspects, even more so in the cross-document setting. This paper makes three key contributions to advance research in this domain. We first extend an existing dataset, the Sci-Arg corpus, by annotating it with explicit inter-document argumentative relations, thereby allowing arguments to be distributed over several documents forming an Argument Web; these new annotations are published using Semantic Web technologies (RDF, OWL). Second, we explore and evaluate three automated approaches for predicting these inter-document argumentative relations, establishing critical baselines on the new dataset. We find that a simple classifier based on discourse indicators with access to context outperforms neural methods. Third, we conduct a comparative analysis of these approaches for both intra- and inter-document settings, identifying statistically significant differences in results that indicate the necessity of distinguishing between these two scenarios. Our findings highlight significant challenges in this complex domain and open crucial avenues for future research on the Argument Web of Science, particularly for those interested in leveraging Semantic Web technologies and knowledge graphs to understand scholarly discourse. With this, we provide the first stepping stones in the form of a benchmark dataset, three baseline methods, and an initial analysis for a systematic exploration of this field relevant to the Web of Data and Science.

Cite as

Florian Ruosch, Cristina Sarasua, and Abraham Bernstein. Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 3, pp. 4:1-4:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{ruosch_et_al:TGDK.3.3.4,
  author =	{Ruosch, Florian and Sarasua, Cristina and Bernstein, Abraham},
  title =	{{Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:33},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{3},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.3.4},
  URN =		{urn:nbn:de:0030-drops-252159},
  doi =		{10.4230/TGDK.3.3.4},
  annote =	{Keywords: Argument Mining, Large Language Models, Knowledge Graphs, Link Prediction}
}

60 Search Results for "Oliveira, Daniel"

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