46 Search Results for "Ito, Hiro"

Volume

LIPIcs, Volume 100

9th International Conference on Fun with Algorithms (FUN 2018)

FUN 2018, June 13-15, 2018, La Maddalena, Italy

Editors: Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe

Document
DOI: 10.4230/LIPIcs.ITCS.2026.47
Dudeney’s Dissection Is Optimal

Authors: Erik D. Demaine, Tonan Kamata, and Ryuhei Uehara

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

Abstract
In 1907, Henry Ernest Dudeney posed a puzzle: "cut any equilateral triangle ... into as few pieces as possible that will fit together and form a perfect square" (without overlap, via translation and rotation). Four weeks later, Dudeney demonstrated a beautiful four-piece solution, which today remains perhaps the most famous example of dissection. In this paper (over a century later), we finally solve Dudeney’s puzzle, by proving that the equilateral triangle and square have no common dissection with three or fewer polygonal pieces. We reduce the problem to the analysis of discrete graph structures representing the correspondence between the edges and the vertices of the pieces forming each polygon.
Cite as

Erik D. Demaine, Tonan Kamata, and Ryuhei Uehara. Dudeney’s Dissection Is Optimal. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.ITCS.2026.47,
  author =	{Demaine, Erik D. and Kamata, Tonan and Uehara, Ryuhei},
  title =	{{Dudeney’s Dissection Is Optimal}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{47:1--47: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.47},
  URN =		{urn:nbn:de:0030-drops-253345},
  doi =		{10.4230/LIPIcs.ITCS.2026.47},
  annote =	{Keywords: Geometric Dissection, Dudeney Dissection, Dissection with Fewest Pieces}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.4
How Pinball Wizards Simulate a Turing Machine

Authors: Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We introduce and investigate the computational complexity of a novel physical problem known as the Pinball Wizard problem. It involves an idealized pinball moving through a maze composed of one-way gates (outswing doors), plane walls, parabolic walls, moving plane walls, and bumpers that cause acceleration or deceleration. Given the initial position and velocity of the pinball, the task is to decide whether it will hit a specified target point. By simulating a two-stack pushdown automaton, we show that the problem is Turing-complete - even in two-dimensional space. In our construction, each step of the automaton corresponds to a constant number of reflections. Thus, deciding the Pinball Wizard problem is at least as hard as the Halting problem. Furthermore, our construction allows bumpers to be replaced with moving walls. In this case, even a ball moving at constant speed - a so-called ray particle - can be used, demonstrating that the Ray Particle Tracing problem is also Turing-complete.
Cite as

Rosemary U. Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer. How Pinball Wizards Simulate a Turing Machine. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{adejoh_et_al:LIPIcs.FSTTCS.2025.4,
  author =	{Adejoh, Rosemary U. and Jakoby, Andreas and Mohanty, Sneha and Schindelhauer, Christian},
  title =	{{How Pinball Wizards Simulate a Turing Machine}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.4},
  URN =		{urn:nbn:de:0030-drops-250832},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.4},
  annote =	{Keywords: Pinball Wizard problem, Halting problem, Turing-complete}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.77
Tolerant Testers for Subgraph-Freeness

Authors: Reut Levi and Jonathan Meiri

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

Abstract
In this paper we study the problem of tolerantly testing the property of being H-free (which also implies distance approximation from being H-free). In the general-graphs model, we show that for tolerant K_k-freeness testing can be achieved with query complexity that is polynomial in the arboricity of the input graph G, arb(G), and independent of the size of G (for graphs in which the average degree is Ω(1)). Specifically for triangles, our algorithm distinguished graphs which are ε-close to being triangle-free from graphs that 3ε(1+η)-far from being triangle-free with expected query complexity which is Õ(arb³(G)) (for constant η and ε). For general k-cliques our algorithm distinguishes graphs which are ε-close to being K_k-free from graphs which are binom(k,2)ε(1+η)-far from being K_k-free with expected query complexity which is polynomial in k, ε, γ and arb(G). We then generalize our result and provide a similar result for any motif H which is 2-connected of radius 1. This includes for example the wheel-graph. Finally, we show that our tester can be applied to the bounded-degree model for tolerantly testing H-freeness for any motif H. The query complexity of the algorithm is polynomial in the degree bound, d, improving the previous state-of-the-art by Marko and Ron (TALG 2009) that obtained quasi-polynomial query complexity in d.
Cite as

Reut Levi and Jonathan Meiri. Tolerant Testers for Subgraph-Freeness. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 77:1-77:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{levi_et_al:LIPIcs.ESA.2025.77,
  author =	{Levi, Reut and Meiri, Jonathan},
  title =	{{Tolerant Testers for Subgraph-Freeness}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{77:1--77:15},
  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.77},
  URN =		{urn:nbn:de:0030-drops-245456},
  doi =		{10.4230/LIPIcs.ESA.2025.77},
  annote =	{Keywords: Tolerant Testing, Property Testing, Subgraph freeness, distance approximation, arboricity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.45
Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them

Authors: Clément L. Canonne, Yun Li, and Seeun William Umboh

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

Abstract
Local Computation Algorithms (LCA), as introduced by Rubinfeld, Tamir, Vardi, and Xie (2011), are a type of ultra-efficient algorithms which, given access to a (large) input for a given computational task, are required to provide fast query access to a consistent output solution, without maintaining a state between queries. This paradigm of computation in particular allows for hugely distributed algorithms, where independent instances of a given LCA provide consistent access to a common output solution. The past decade has seen a significant amount of work on LCAs, by and large focusing on graph problems. In this paper, we initiate the study of Local Computation Algorithms for perhaps the archetypal combinatorial optimization problem, Knapsack. We first establish strong impossibility results, ruling out the existence of any non-trivial LCA for Knapsack as several of its relaxations. We then show how equipping the LCA with additional access to the Knapsack instance, namely, weighted item sampling, allows one to circumvent these impossibility results, and obtain sublinear-time and query LCAs. Our positive result draws on a connection to the recent notion of reproducibility for learning algorithms (Impagliazzo, Lei, Pitassi, and Sorrell, 2022), a connection we believe to be of independent interest for the design of LCAs.
Cite as

Clément L. Canonne, Yun Li, and Seeun William Umboh. Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{canonne_et_al:LIPIcs.APPROX/RANDOM.2025.45,
  author =	{Canonne, Cl\'{e}ment L. and Li, Yun and Umboh, Seeun William},
  title =	{{Local Computation Algorithms for Knapsack: Impossibility Results, and How to Avoid Them}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{45:1--45:21},
  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.45},
  URN =		{urn:nbn:de:0030-drops-244111},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.45},
  annote =	{Keywords: Local computation algorithms, Knapsack, algorithms, lower bounds}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.32
Quantum Property Testing in Sparse Directed Graphs

Authors: Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó

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

Abstract
We initiate the study of quantum property testing in sparse directed graphs, and more particularly in the unidirectional model, where the algorithm is allowed to query only the outgoing edges of a vertex. In the classical unidirectional model, the problem of testing k-star-freeness, and more generally k-source-subgraph-freeness, is almost maximally hard for large k. We prove that this problem has almost quadratic advantage in the quantum setting. Moreover, we show that this advantage is nearly tight, by showing a quantum lower bound using the method of dual polynomials on an intermediate problem for a new, property testing version of the k-collision problem that was not studied before. To illustrate that not all problems in graph property testing admit such a quantum speedup, we consider the problem of 3-colorability in the related undirected bounded-degree model, when graphs are now undirected. This problem is maximally hard to test classically, and we show that also quantumly it requires a linear number of queries.
Cite as

Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó. Quantum Property Testing in Sparse Directed Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.APPROX/RANDOM.2025.32,
  author =	{Apers, Simon and Magniez, Fr\'{e}d\'{e}ric and Sen, Sayantan and Szab\'{o}, D\'{a}niel},
  title =	{{Quantum Property Testing in Sparse Directed Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{32:1--32:24},
  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.32},
  URN =		{urn:nbn:de:0030-drops-243987},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.32},
  annote =	{Keywords: property testing, quantum computing, bounded-degree directed graphs, dual polynomial method, collision finding}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.61
A Fast Coloring Oracle for Average Case Hypergraphs

Authors: Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber

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

Abstract
Hypergraph 2-colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over a uniformly chosen 2-colorable 3-uniform hypergraph. Lee, Molla, and Nagle recently extended this to k-uniform hypergraphs for all k ≥ 3. Both papers relied heavily on the regularity lemma, hence their analysis was involved and their running time hid tower-type constants. Our first result in this paper is a new simple and elementary deterministic 2-coloring algorithm that reproves the theorems of Person-Schacht and Lee-Molla-Nagle while avoiding the use of the regularity lemma. We also show how to turn our new algorithm into a randomized one with average expected running time of only O(n). Our second and main result gives what we consider to be the ultimate evidence of just how easy it is to find a 2-coloring of an average 2-colorable hypergraph. We define a coloring oracle to be an algorithm which, given vertex v, assigns color red/blue to v while inspecting as few edges as possible, so that the answers to any sequence of queries to the oracle are consistent with a single legal 2-coloring of the input. Surprisingly, we show that there is a coloring oracle that, on average, can answer every vertex query in time O(1).
Cite as

Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, and Shlomo Tauber. A Fast Coloring Oracle for Average Case Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 61:1-61:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marcussen_et_al:LIPIcs.APPROX/RANDOM.2025.61,
  author =	{Marcussen, Cassandra and Pyne, Edward and Rubinfeld, Ronitt and Shapira, Asaf and Tauber, Shlomo},
  title =	{{A Fast Coloring Oracle for Average Case Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{61:1--61:13},
  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.61},
  URN =		{urn:nbn:de:0030-drops-244272},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.61},
  annote =	{Keywords: average-case algorithms, local computation algorithms, graph coloring}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.116
A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time

Authors: Sepideh Mahabadi, Mohammad Roghani, and Jakub Tarnawski

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bounds are known for it. Our result is a 0.5109-approximation algorithm with a running time of Õ(n√n). All previous algorithms either provide only a marginal improvement (e.g., 2^{-280}) over the 0.5-approximation that arises from estimating a maximal matching, or have a running time that is nearly n². Our approach is also arguably much simpler than other algorithms beating 0.5-approximation.
Cite as

Sepideh Mahabadi, Mohammad Roghani, and Jakub Tarnawski. A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 116:1-116:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mahabadi_et_al:LIPIcs.ICALP.2025.116,
  author =	{Mahabadi, Sepideh and Roghani, Mohammad and Tarnawski, Jakub},
  title =	{{A 0.51-Approximation of Maximum Matching in Sublinear n^\{1.5\} Time}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{116:1--116:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.116},
  URN =		{urn:nbn:de:0030-drops-234932},
  doi =		{10.4230/LIPIcs.ICALP.2025.116},
  annote =	{Keywords: Sublinear Algorithms, Maximum Matching, Maximal Matching, Approximation Algorithm}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.74
Sublinear Metric Steiner Tree via Improved Bounds for Set Cover

Authors: Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We study the metric Steiner tree problem in the sublinear query model. In this problem, for a set of n points V in a metric space given to us by means of query access to an n× n matrix w, and a set of terminals T ⊆ V, the goal is to find the minimum-weight subset of the edges that connects all the terminal vertices. Recently, Chen, Khanna and Tan [SODA'23] gave an algorithm that uses Õ(n^{13/7}) queries and outputs a (2-η)-estimate of the metric Steiner tree weight, where η > 0 is a universal constant. A key component in their algorithm is a sublinear algorithm for a particular set cover problem where, given a set system (𝒰, ℱ), the goal is to provide a multiplicative-additive estimate for |𝒰|-SC(𝒰, ℱ). Here 𝒰 is the set of elements, ℱ is the collection of sets, and SC(𝒰, ℱ) denotes the optimal set cover size of (𝒰, ℱ). In particular, their algorithm returns a (1/4, ε⋅|𝒰|)-multiplicative-additive estimate for this set cover problem using Õ(|ℱ|^{7/4}) membership oracle queries (querying whether a set S ∈ 𝒮 contains an element e ∈ 𝒰), where ε is a fixed constant. In this work, we improve the query complexity of (2-η)-estimating the metric Steiner tree weight to Õ(n^{5/3}) by showing a (1/2, ε⋅|𝒰|)-estimate for the above set cover problem using Õ(|ℱ|^{5/3}) membership queries. To design our set cover algorithm, we estimate the size of a random greedy maximal matching for an auxiliary multigraph that the algorithm constructs implicitly, without access to its adjacency list or matrix. Previous analyses of random greedy maximal matching have focused on simple graphs, assuming access to their adjacency list or matrix. To address this, we extend the analysis of Behnezhad [FOCS'21] of random greedy maximal matching on simple graphs to multigraphs, and prove additional properties that may be of independent interest.
Cite as

Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian. Sublinear Metric Steiner Tree via Improved Bounds for Set Cover. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 74:1-74:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mahabadi_et_al:LIPIcs.ITCS.2025.74,
  author =	{Mahabadi, Sepideh and Roghani, Mohammad and Tarnawski, Jakub and Vakilian, Ali},
  title =	{{Sublinear Metric Steiner Tree via Improved Bounds for Set Cover}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{74:1--74:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.74},
  URN =		{urn:nbn:de:0030-drops-227029},
  doi =		{10.4230/LIPIcs.ITCS.2025.74},
  annote =	{Keywords: Sublinear Algorithms, Steiner Tree, Set Cover, Maximum Matching, Approximation Algorithm}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.34
Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries

Authors: François Le Gall, Oran Nadler, Harumichi Nishimura, and Rotem Oshman

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more.
Cite as

François Le Gall, Oran Nadler, Harumichi Nishimura, and Rotem Oshman. Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.OPODIS.2024.34,
  author =	{Le Gall, Fran\c{c}ois and Nadler, Oran and Nishimura, Harumichi and Oshman, Rotem},
  title =	{{Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.34},
  URN =		{urn:nbn:de:0030-drops-225701},
  doi =		{10.4230/LIPIcs.OPODIS.2024.34},
  annote =	{Keywords: SMP model, multi-party communication, quantum distributed algorithms}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.FUN.2018
LIPIcs, Volume 100, FUN'18, Complete Volume

Authors: Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
LIPIcs, Volume 100, FUN'18, Complete Volume
Cite as

9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{ito_et_al:LIPIcs.FUN.2018,
  title =	{{LIPIcs, Volume 100, FUN'18, Complete Volume}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018},
  URN =		{urn:nbn:de:0030-drops-89311},
  doi =		{10.4230/LIPIcs.FUN.2018},
  annote =	{Keywords: Theory of computation, Complexity classes, Algorithm design techniques, Computability, Approximation algorithms analysis, Mathematics of computing}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FUN.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Hiro Ito, Stefano Leonardi, Linda Pagli, and Giuseppe Prencipe

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 0:i-0:xi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.FUN.2018.0,
  author =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{0:i--0:xi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.0},
  URN =		{urn:nbn:de:0030-drops-87914},
  doi =		{10.4230/LIPIcs.FUN.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.FUN.2018.1
Mind the Gap (Invited Paper)

Authors: Martín Farach-Colton

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
As a New Yorker, I'm painfully aware of space. There is, after all, nothing more luxurious than empty space! So when it comes to algorithms, I'm all in favor of leaving holes in my data structures. In this talk, I'll explore the advantages of pampering algorithms with some much needed breathing room.
Cite as

Martín Farach-Colton. Mind the Gap (Invited Paper). In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{farachcolton:LIPIcs.FUN.2018.1,
  author =	{Farach-Colton, Mart{\'\i}n},
  title =	{{Mind the Gap}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.1},
  URN =		{urn:nbn:de:0030-drops-87924},
  doi =		{10.4230/LIPIcs.FUN.2018.1},
  annote =	{Keywords: library sort, Italian island, packed memory arrays, weight balanced trees, Italians know how to throw a conference}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.FUN.2018.2
Evolution of Impossible Objects (Invited Paper)

Authors: Kokichi Sugihara

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Impossible objects - 3D objects that can create a visual effect that seems impossible - can be classified by generation based on the order in which they were discovered or produced. The first generation consists of objects whose appearance when observed from a certain viewpoint matches a picture of an impossible object. Many such objects can be created, as there are multiple 3D objects that will project the same two-dimensional picture, including shapes that the human vision system is unable to perceive. The gap between the mathematical and the psychological can also create other types of "impossible" visual effects. Impossible objects are here classified into seven groups.
Cite as

Kokichi Sugihara. Evolution of Impossible Objects (Invited Paper). In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 2:1-2:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sugihara:LIPIcs.FUN.2018.2,
  author =	{Sugihara, Kokichi},
  title =	{{Evolution of Impossible Objects}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{2:1--2:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.2},
  URN =		{urn:nbn:de:0030-drops-87939},
  doi =		{10.4230/LIPIcs.FUN.2018.2},
  annote =	{Keywords: Ambiguous cylinder, anomalous picture, impossible motion, impossible object, optical illusion}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.3
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

Authors: Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw a path in a rectangular grid graph from a start vertex to a destination vertex. The different puzzle types place different constraints on the path: preventing some edges from being visited (broken edges); forcing some edges or vertices to be visited (hexagons); forcing some cells to have certain numbers of incident path edges (triangles); or forcing the regions formed by the path to be partially monochromatic (squares), have exactly two special cells (stars), or be singly covered by given shapes (polyominoes) and/or negatively counting shapes (antipolyominoes). We show that any one of these clue types (except the first) is enough to make path finding NP-complete ("witnesses exist but are hard to find"), even for rectangular boards. Furthermore, we show that a final clue type (antibody), which necessarily "cancels" the effect of another clue in the same region, makes path finding Sigma_2-complete ("witnesses do not exist"), even with a single antibody (combined with many anti/polyominoes), and the problem gets no harder with many antibodies.
Cite as

Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy. Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abel_et_al:LIPIcs.FUN.2018.3,
  author =	{Abel, Zachary and Bosboom, Jeffrey and Demaine, Erik D. and Hamilton, Linus and Hesterberg, Adam and Kopinsky, Justin and Lynch, Jayson and Rudoy, Mikhail},
  title =	{{Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.3},
  URN =		{urn:nbn:de:0030-drops-87944},
  doi =		{10.4230/LIPIcs.FUN.2018.3},
  annote =	{Keywords: video games, puzzles, hardness}
}
  • Refine by Type
  • 45 Document/PDF
  • 9 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 1 2026
  • 8 2025
  • 35 2018
  • 2 2016

  • Refine by Author
  • 5 Demaine, Erik D.
  • 4 Ito, Hiro
  • 4 Lynch, Jayson
  • 3 Leucci, Stefano
  • 3 Rudoy, Mikhail
  • Show More...

  • Refine by Series/Journal
  • 45 LIPIcs

  • Refine by Classification
  • 14 Theory of computation → Problems, reductions and completeness
  • 6 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 2 Mathematics of computing → Combinatoric problems
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 4 computational complexity
  • 4 hardness
  • 3 video games
  • 2 Approximation Algorithm
  • 2 Maximum Matching
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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