DROPS

Document

DOI: 10.4230/LIPIcs.FORC.2026.13

Inducing Efficient and Equitable Professional Networks Through Link Recommendations

Authors: Cynthia Dwork, Chris Hays, Lunjia Hu, Nicole Immorlica, and Juan Perdomo

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract

Professional networks are a key determinant of individuals’ labor market outcomes. They may also play a role in either exacerbating or ameliorating inequality of opportunity across social groups. We initiate an investigation into the positive role that a professional networking platform can play when network members have different degrees of off-platform privilege. In a theoretical model, we show that the set of link recommendation policies that reduce costs between privileged and unprivileged individuals yield equilibria that are welfare-improving over all possible equilibria, compared to those obtained when not recommending links or recommending some smaller fraction of cross-group links. We next investigate the implications of platforms that do not intervene on the network formation process. We show that, absent intervention, inequality can increase relative to starting privilege levels even without exogenous in-group preferences, confirming and complementing existing theoretical literature. Increased inequality emerges from the differential leverage privileged and unprivileged individuals have in forming connections due to their asymmetric ex ante prospects. This is a formalization of a source of inequality in the labor market which has not been previously explored. These two findings reveal a stark reality: professional networking platforms that fail to foster integration in the link formation process risk reducing the platform’s utility to its users and exacerbating existing labor market inequality.

Cite as

Cynthia Dwork, Chris Hays, Lunjia Hu, Nicole Immorlica, and Juan Perdomo. Inducing Efficient and Equitable Professional Networks Through Link Recommendations. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dwork_et_al:LIPIcs.FORC.2026.13,
  author =	{Dwork, Cynthia and Hays, Chris and Hu, Lunjia and Immorlica, Nicole and Perdomo, Juan},
  title =	{{Inducing Efficient and Equitable Professional Networks Through Link Recommendations}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.13},
  URN =		{urn:nbn:de:0030-drops-259863},
  doi =		{10.4230/LIPIcs.FORC.2026.13},
  annote =	{Keywords: Professional networks, Inequality, Link Recommendations}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.25

The Typical Algebraic Shifting of Graphs and Surfaces

Authors: Denys Bulavka, Eran Nevo, and Yuval Peled

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

We initiate a statistical study of Kalai’s exterior algebraic shifting, focusing on concentration phenomena for random triangulations of a fixed space. First, for a uniform n-vertex refinement of any given graph G, we show that asymptotically almost-surely (a.a.s.) its exterior algebraic shifting is an explicit shifted graph depending only on n and the Betti numbers of G. Next, for any given compact connected Riemannian surface S, sample n points independently at random according to the volume measure, and consider the resulted a.a.s. unique Delaunay triangulation. We prove that a.a.s. its exterior algebraic shifting is an explicit shifted complex depending only on n and the Euler genus of S, and in particular is area-rigid. In both results the expected shifted complex is a homology lex-segment complex, a notion we define combinatorially and characterize numerically à la Björner-Kalai. As a tool to prove the result on surfaces, we prove a universality result on edge contractions: for every fixed surface triangulation K, every dense enough point set in the surface yields a Delaunay triangulation that edge contracts to K.

Cite as

Denys Bulavka, Eran Nevo, and Yuval Peled. The Typical Algebraic Shifting of Graphs and Surfaces. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bulavka_et_al:LIPIcs.SoCG.2026.25,
  author =	{Bulavka, Denys and Nevo, Eran and Peled, Yuval},
  title =	{{The Typical Algebraic Shifting of Graphs and Surfaces}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.25},
  URN =		{urn:nbn:de:0030-drops-258312},
  doi =		{10.4230/LIPIcs.SoCG.2026.25},
  annote =	{Keywords: Algebraic shifting, Delaunay triangulation, surfaces, random triangulation, area rigidity}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.73

The Complete 10-Tetrahedra Census of Orientable Cusped Hyperbolic 3-Manifolds

Authors: Shana Yunsheng Li

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

We extend the complete census of orientable cusped hyperbolic 3-manifolds to 10 tetrahedra, giving the next 150,730 manifolds and their 496,638 minimal ideal triangulations. As applications, we find the precisely 439,898 exceptional Dehn fillings on them, revealing the next 1,849 simplest hyperbolic knot exteriors in S³. We also give the simplest example of an orientable cusped hyperbolic 3-manifold containing a closed totally geodesic surface.

Cite as

Shana Yunsheng Li. The Complete 10-Tetrahedra Census of Orientable Cusped Hyperbolic 3-Manifolds. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li:LIPIcs.SoCG.2026.73,
  author =	{Li, Shana Yunsheng},
  title =	{{The Complete 10-Tetrahedra Census of Orientable Cusped Hyperbolic 3-Manifolds}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{73:1--73:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.73},
  URN =		{urn:nbn:de:0030-drops-258800},
  doi =		{10.4230/LIPIcs.SoCG.2026.73},
  annote =	{Keywords: hyperbolic manifolds, 3-manifolds, triangulation, census, tabulation, exact computation, computational topology, low-dimensional topology}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.79

D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence

Authors: Soham Mukherjee, Shreyas N. Samaga, Cheng Xin, Steve Oudot, and Tamal K. Dey

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

End-to-end topological learning using 1-parameter persistence is well-known. We show that the framework can be enhanced using 2-parameter persistence by adopting a recently introduced 2-parameter persistence based vectorization technique called Gril. We establish a theory for gradient descent on Gril producing D-Gril. We show that D-Gril can be used to learn a bifiltration function on benchmark graph datasets. Further, we exhibit that this framework can be applied in the context of bio-activity prediction in drug discovery.

Cite as

Soham Mukherjee, Shreyas N. Samaga, Cheng Xin, Steve Oudot, and Tamal K. Dey. D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 79:1-79:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.SoCG.2026.79,
  author =	{Mukherjee, Soham and Samaga, Shreyas N. and Xin, Cheng and Oudot, Steve and Dey, Tamal K.},
  title =	{{D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{79:1--79:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.79},
  URN =		{urn:nbn:de:0030-drops-258865},
  doi =		{10.4230/LIPIcs.SoCG.2026.79},
  annote =	{Keywords: Topological Data Analysis, Persistent Homology, Multiparameter Persistence, Graph Learning, Graph Neural Networks}
}

Document

DOI: 10.4230/OASIcs.NINeS.2026.24

SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing

Authors: Siddhant Ray, Xi Jiang, Jack Luo, Nick Feamster, and Junchen Jiang

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract

Low Latency, Low Loss, and Scalable Throughput (L4S), as an emerging router-queue management technique, has seen steady deployment in the industry. An L4S-enabled router assigns each packet to the queue based on the packet header marking. Currently, L4S employs per-flow queue selection, i.e., all packets of a flow are marked the same way and thus use the same queues, even though each packet is marked separately. However, this may hurt tail latency and latency-sensitive applications because transient congestion and queue buildups may only affect a fraction of packets in a flow. We present SwiftQueue, a new L4S queue-selection strategy in which a sender uses a novel per-packet latency predictor to pinpoint which packets likely have latency spikes or drops. The insight is that many packet-level latency variations result from complex interactions among recent packets at shared router queues. Yet, these intricate packet-level latency patterns are hard to learn efficiently by traditional models. Instead, SwiftQueue uses a custom Transformer, which is well-studied for its expressiveness on sequential patterns, to predict the next packet’s latency based on the latencies of recently received ACKs. Based on the predicted latency of each outgoing packet, SwiftQueue’s sender dynamically marks the L4S packet header to assign packets to potentially different queues, even within the same flow. Using real network traces, we show that SwiftQueue is 45-65% more accurate in predicting latency and its variations than state-of-art methods. Based on its latency prediction, SwiftQueue reduces the tail latency for L4S-enabled flows by 36-45%, compared with the existing L4S queue-selection method.

Cite as

Siddhant Ray, Xi Jiang, Jack Luo, Nick Feamster, and Junchen Jiang. SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 24:1-24:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ray_et_al:OASIcs.NINeS.2026.24,
  author =	{Ray, Siddhant and Jiang, Xi and Luo, Jack and Feamster, Nick and Jiang, Junchen},
  title =	{{SwiftQueue: Optimizing Low-Latency Applications with Swift Packet Queuing}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{24:1--24:29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.24},
  URN =		{urn:nbn:de:0030-drops-256093},
  doi =		{10.4230/OASIcs.NINeS.2026.24},
  annote =	{Keywords: Latency prediction, L4S Queue Management}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.49

2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs

Authors: Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf

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

Abstract

Minimally rigid graphs can be decided and embedded in the plane efficiently, i.e. in polynomial time. There is also an efficient randomized parallel algorithm, i.e. in RNC. We present an NC-algorithm to decide whether one-crossing-minor-free graphs are minimally rigid. In the special case of K_{3,3}-free graphs, we also compute an infinitesimally rigid embedding in NC.

Cite as

Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf. 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.STACS.2026.49,
  author =	{Gurjar, Rohit and Rothmund, Kilian and Thierauf, Thomas},
  title =	{{2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{49:1--49:22},
  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.49},
  URN =		{urn:nbn:de:0030-drops-255385},
  doi =		{10.4230/LIPIcs.STACS.2026.49},
  annote =	{Keywords: Graph Rigidity, Parallel Algorithms, Polynomial Identity Testing, Derandomization}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.35

Symmetric Quantum Computation

Authors: Davi Castro-Silva, Tom Gur, and Sergii Strelchuk

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

Abstract

We introduce a systematic study of symmetric quantum circuits, a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model is well-adapted for studying the role of symmetry in quantum speedups, extending a central notion of symmetric computation studied in the classical setting. Our results establish that symmetric quantum circuits are fundamentally more powerful than their classical counterparts. First, we give efficient symmetric circuits for key quantum techniques such as amplitude amplification, phase estimation and linear combination of unitaries. In addition, we show how the task of symmetric state preparation can be performed efficiently in several natural cases. Finally, we demonstrate an exponential separation in the symmetric setting for the problem XOR-SAT, which requires exponential-size symmetric classical circuits but can be solved by polynomial-size symmetric quantum circuits.

Cite as

Davi Castro-Silva, Tom Gur, and Sergii Strelchuk. Symmetric Quantum Computation. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 35:1-35:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{castrosilva_et_al:LIPIcs.ITCS.2026.35,
  author =	{Castro-Silva, Davi and Gur, Tom and Strelchuk, Sergii},
  title =	{{Symmetric Quantum Computation}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{35:1--35:10},
  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.35},
  URN =		{urn:nbn:de:0030-drops-253223},
  doi =		{10.4230/LIPIcs.ITCS.2026.35},
  annote =	{Keywords: Quantum computing, complexity theory, symmetries}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.96

Robust Resource Allocation via Competitive Subsidies

Authors: David X. Lin, Giannis Fikioris, Siddhartha Banerjee, and Éva Tardos

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

Abstract

A canonical setting for non-monetary online resource allocation is one where agents compete over multiple rounds for a single item per round, with i.i.d. valuations and additive utilities across rounds. With n symmetric agents, a natural benchmark for each agent is the utility realized by her favorite 1/n-fraction of rounds; a line of work has demonstrated one can robustly guarantee each agent a constant fraction of this ideal utility, irrespective of how other agents behave. In particular, several mechanisms have been shown to be 1/2-robust, and recent work established that repeated first-price auctions based on artificial credits have a robustness factor of 0.59, which cannot be improved beyond 0.6 using first-price and simple strategies. In contrast, even without strategic considerations, the best achievable factor is 1-1/e≈ 0.63. In this work, we break the 0.6 first-price barrier to get a new 0.625-robust mechanism, which almost closes the gap to the non-strategic robustness bound. Surprisingly, we do so via a simple auction, where in each round, bidders decide if they ask for the item, and we allocate uniformly at random among those who ask. The main new ingredient is the idea of competitive subsidies, wherein we charge the winning agent an amount in artificial credits that decreases when fewer agents are bidding (specifically, when k agents bid, then the winner pays proportional to k/(k+1), varying the payment by a factor of 2 depending on the competition). Moreover, we show how it can be modified to get an equilibrium strategy with a slightly weaker robust guarantee of 5/(3e) ≈ 0.61 (and the optimal 1-1/e factor at equilibrium). Finally, we show that our mechanism gives the best possible bound under a wide class of auction-based mechanisms.

Cite as

David X. Lin, Giannis Fikioris, Siddhartha Banerjee, and Éva Tardos. Robust Resource Allocation via Competitive Subsidies. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 96:1-96:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ITCS.2026.96,
  author =	{Lin, David X. and Fikioris, Giannis and Banerjee, Siddhartha and Tardos, \'{E}va},
  title =	{{Robust Resource Allocation via Competitive Subsidies}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{96:1--96: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.96},
  URN =		{urn:nbn:de:0030-drops-253835},
  doi =		{10.4230/LIPIcs.ITCS.2026.96},
  annote =	{Keywords: Online Resource Allocation, Non-Monetary Mechanisms}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.91

Limitations of Membership Queries in Testable Learning

Authors: Jane Lange and Mingda Qiao

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

Abstract

Membership queries (MQ) often yield speedups for learning tasks, particularly in the distribution-specific setting. We show that in the testable learning model of Rubinfeld and Vasilyan [Rubinfeld and Vasilyan, 2023], membership queries cannot decrease the time complexity of testable learning algorithms beyond the complexity of sample-only distribution-specific learning. In the testable learning model, the learner must output a hypothesis whenever the data distribution satisfies a desired property, and if it outputs a hypothesis, the hypothesis must be near-optimal. We give a general reduction from sample-based refutation of boolean concept classes, as presented in [Vadhan, 2017; Kothari and Livni, 2018], to testable learning with queries (TL-Q). This yields lower bounds for TL-Q via the reduction from learning to refutation given in [Kothari and Livni, 2018]. The result is that, relative to a concept class and a distribution family, no m-sample TL-Q algorithm can be super-polynomially more time-efficient than the best m-sample PAC learner. Finally, we define a class of "statistical" MQ algorithms that encompasses many known distribution-specific MQ learners, such as those based on influence estimation or subcube-conditional statistical queries. We show that TL-Q algorithms in this class imply efficient statistical-query refutation and learning algorithms. Thus, combined with known SQ dimension lower bounds, our results imply that these efficient membership query learners cannot be made testable.

Cite as

Jane Lange and Mingda Qiao. Limitations of Membership Queries in Testable Learning. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 91:1-91:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lange_et_al:LIPIcs.ITCS.2026.91,
  author =	{Lange, Jane and Qiao, Mingda},
  title =	{{Limitations of Membership Queries in Testable Learning}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{91:1--91:23},
  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.91},
  URN =		{urn:nbn:de:0030-drops-253785},
  doi =		{10.4230/LIPIcs.ITCS.2026.91},
  annote =	{Keywords: Testable learning, PAC learning}
}

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

Resource

DOI: 10.4230/TGDK.3.3.3

Supporting Psychometric Instrument Usage Through the POEM Ontology

Authors: Kelsey Rook, Henrique Santos, Deborah L. McGuinness, Manuel S. Sprung, Paulo Pinheiro, and Bruce F. Chorpita

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

Abstract

Psychometrics is the field relating to the measurement of concepts within psychology, particularly the assessment of various social and psychological dimensions in humans. The relationship between psychometric entities is critical to finding an appropriate assessment instrument, especially in the context of clinical psychology and mental healthcare in which providing the best care based on empirical evidence is crucial. We aim to model these entities, which include psychometric questionnaires and their component elements, the subject and respondent, and the latent variables being assessed. The current standard for questionnaire-based assessment relies on text-based distributions of instruments; so, a structured representation is necessary to capture these relationships to enhance accessibility and use of existing measures, encourage reuse of questionnaires and their component elements, and enable sophisticated reasoning over assessment instruments and results by increasing interoperability. We present the design process and architecture of such a domain ontology, the Psychometric Ontology of Experiences and Measures, situating it within the context of related ontologies, and demonstrating its practical utility through evaluation against a series of competency questions concerning the creation, use, and reuse of psychometric questionnaires in clinical, research, and development settings.

Cite as

Kelsey Rook, Henrique Santos, Deborah L. McGuinness, Manuel S. Sprung, Paulo Pinheiro, and Bruce F. Chorpita. Supporting Psychometric Instrument Usage Through the POEM Ontology. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 3, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{rook_et_al:TGDK.3.3.3,
  author =	{Rook, Kelsey and Santos, Henrique and McGuinness, Deborah L. and Sprung, Manuel S. and Pinheiro, Paulo and Chorpita, Bruce F.},
  title =	{{Supporting Psychometric Instrument Usage Through the POEM Ontology}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:19},
  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.3},
  URN =		{urn:nbn:de:0030-drops-252148},
  doi =		{10.4230/TGDK.3.3.3},
  annote =	{Keywords: ontology, ontology development, psychometric assessment, psychometric ontology}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.23

The Price of Connectivity Augmentation on Planar Graphs

Authors: Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.

Cite as

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt. The Price of Connectivity Augmentation on Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.GD.2025.23,
  author =	{A. Akitaya, Hugo and Dallant, Justin and Demaine, Erik D. and Kaufmann, Michael and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D. and Ueckerdt, Torsten},
  title =	{{The Price of Connectivity Augmentation on Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.23},
  URN =		{urn:nbn:de:0030-drops-250095},
  doi =		{10.4230/LIPIcs.GD.2025.23},
  annote =	{Keywords: connectivity augmentation, local crossing number, flip distance}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2025.62

Brief Announcement: Time, Fences and the Ordering of Events in TSO

Authors: Raïssa Nataf and Yoram Moses

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

Abstract

Total Store Order (TSO) is one of the most popular relaxed memory model in multiprocessor architectures, widely implemented, for example, in Intel’s x86 and x64 platforms. It delays write visibility via store buffers, thereby allowing a significant improvement in efficiency. This, however, complicates reasoning about correctness, as executions may violate sequential consistency. We present a semantic framework that provides effective tools that can pinpoint when such synchronization is necessary under TSO. We define a TSO-specific occurs-before relation, adapting Lamport’s happens-before to TSO, and prove that events at different sites can be temporally ordered only via an occurs-before chain. Analyzing how fences and RMWs create these chains lets us identify when they are unavoidable. We present in this BA how these results impact linearizable implementations of registers, capturing information flow and causality in TSO. The full version of this work provides details as well as results regarding the need for synchronization in linearizable implementations of additional objects.

Cite as

Raïssa Nataf and Yoram Moses. Brief Announcement: Time, Fences and the Ordering of Events in TSO. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 62:1-62:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nataf_et_al:LIPIcs.DISC.2025.62,
  author =	{Nataf, Ra\"{i}ssa and Moses, Yoram},
  title =	{{Brief Announcement: Time, Fences and the Ordering of Events in TSO}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{62:1--62: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.62},
  URN =		{urn:nbn:de:0030-drops-248784},
  doi =		{10.4230/LIPIcs.DISC.2025.62},
  annote =	{Keywords: TSO, linearizability, happens before, fences, synchronization actions}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.21

A Unified FPT Framework for Crossing Number Problems

Authors: Éric Colin de Verdière and Petr Hliněný

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework that smoothly captures many generalized crossing number problems, and that yields fixed-parameter tractable (FPT) algorithms for them not only in the plane but also on surfaces. Our framework takes the following form. We fix a surface S, an integer r, and a map κ from the set of topological drawings of graphs in S to ℤ_+ ∪ {∞}, satisfying some natural monotonicity conditions, but essentially describing the allowed drawings and how we want to count the crossings in them. Then deciding whether an input graph G has an allowed drawing D on S with κ(D) ≤ r can be done in time quadratic in the size of G (and exponential in other parameters). More generally, we may take as input an edge-colored graph, and distinguish crossings by the colors of the involved edges; and we may allow to perform a bounded number of edge removals and vertex splits to G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This framework implies, in a unified way, quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle’s metatheorem, but for many of those, we obtain an algorithm with a better runtime. Moreover, our framework extends, at no cost, to these crossing number variants in any fixed surface.

Cite as

Éric Colin de Verdière and Petr Hliněný. A Unified FPT Framework for Crossing Number Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2025.21,
  author =	{Colin de Verdi\`{e}re, \'{E}ric and Hlin\v{e}n\'{y}, Petr},
  title =	{{A Unified FPT Framework for Crossing Number Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.21},
  URN =		{urn:nbn:de:0030-drops-244897},
  doi =		{10.4230/LIPIcs.ESA.2025.21},
  annote =	{Keywords: computational geometry, fixed-parameter tractability, graph drawing, graph embedding, crossing number, two-dimensional simplicial complex, surface}
}

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.17

Spectral Refutations of Semirandom k-LIN over Larger Fields

Authors: Nicholas Kocurek and Peter Manohar

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

Abstract

We study the problem of strongly refuting semirandom k-LIN(𝔽) instances: systems of k-sparse inhomogeneous linear equations over a finite field 𝔽. For the case of 𝔽 = 𝔽₂, this is the well-studied problem of refuting semirandom instances of k-XOR, where the works of [Venkatesan Guruswami et al., 2022; Jun-Ting Hsieh et al., 2023] establish a tight trade-off between runtime and clause density for refutation: for any choice of a parameter 𝓁, they give an n^{O(𝓁)}-time algorithm to certify that there is no assignment that can satisfy more than 1/2 + ε-fraction of constraints in a semirandom k-XOR instance, provided that the instance has O(n)⋅(n/𝓁)^{k/2 - 1} log n/ε⁴ constraints, and the work of [Pravesh K. Kothari et al., 2017] provides good evidence that this tight up to a polylog(n) factor via lower bounds for the Sum-of-Squares hierarchy. However, for larger fields, the only known results for this problem are established via black-box reductions to the case of 𝔽₂, resulting in a |𝔽|^{3k} gap between the current best upper and lower bounds. In this paper, we give an algorithm for refuting semirandom k-LIN(𝔽) instances with the "correct" dependence on the field size |𝔽|. For any choice of a parameter 𝓁, our algorithm runs in (|𝔽|)^O(𝓁)-time and strongly refutes semirandom k-LIN(𝔽) instances with at least O(n) ⋅ (|𝔽^*| n/𝓁) ^{k/2 - 1} log(n|𝔽^*|)/ε⁴ constraints. We give good evidence that this dependence on the field size |𝔽| is optimal by proving a lower bound for the Sum-of-Squares hierarchy that matches this threshold up to a polylog(n |𝔽^*|) factor. Our results also extend beyond finite fields to the more general case of ℤ_m and arbitrary finite Abelian groups. Our key technical innovation is a generalization of the "𝔽₂ Kikuchi matrices" of [Alexander S. Wein et al., 2019; Venkatesan Guruswami et al., 2022] to larger fields, and finite Abelian groups more generally.

Cite as

Nicholas Kocurek and Peter Manohar. Spectral Refutations of Semirandom k-LIN over Larger Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kocurek_et_al:LIPIcs.APPROX/RANDOM.2025.17,
  author =	{Kocurek, Nicholas and Manohar, Peter},
  title =	{{Spectral Refutations of Semirandom k-LIN over Larger Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.17},
  URN =		{urn:nbn:de:0030-drops-243834},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.17},
  annote =	{Keywords: Spectral Algorithms, CSP Refutation, Kikuchi Matrices}
}

40 Search Results for "Jackson, Michael"

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