7 Search Results for "Amano, Kazuyuki"

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.CCC.2025.36
Lifting with Colourful Sunflowers

Authors: Susanna F. de Rezende and Marc Vinyals

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We show that a generalization of the DAG-like query-to-communication lifting theorem, when proven using sunflowers over non-binary alphabets, yields lower bounds on the monotone circuit complexity and proof complexity of natural functions and formulas that are better than previously known results obtained using the approximation method. These include an n^Ω(k) lower bound for the clique function up to k ≤ n^{1/2-ε}, and an exp(Ω(n^{1/3-ε})) lower bound for a function in P.
Cite as

Susanna F. de Rezende and Marc Vinyals. Lifting with Colourful Sunflowers. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{derezende_et_al:LIPIcs.CCC.2025.36,
  author =	{de Rezende, Susanna F. and Vinyals, Marc},
  title =	{{Lifting with Colourful Sunflowers}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{36:1--36:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.36},
  URN =		{urn:nbn:de:0030-drops-237303},
  doi =		{10.4230/LIPIcs.CCC.2025.36},
  annote =	{Keywords: lifting, sunflower, clique, colouring, monotone circuit, cutting planes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.42
Local Enumeration: The Not-All-Equal Case

Authors: Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, and Navid Talebanfard

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number k and a parameter t, given an n-variate k-CNF with no satisfying assignment of Hamming weight less than t(n), enumerate all satisfying assignments of Hamming weight exactly t(n). Furthermore, they gave a randomized algorithm for Enum(k, t) and employed new ideas to analyze the first non-trivial case, namely k = 3. In particular, they solved Enum(3, n/2) in expected 1.598ⁿ time. A simple construction shows a lower bound of 6^{n/4} ≈ 1.565ⁿ. In this paper, we show that to break SSETH, it is sufficient to consider a simpler local enumeration problem NAE-Enum(k, t): for a natural number k and a parameter t, given an n-variate k-CNF with no satisfying assignment of Hamming weight less than t(n), enumerate all Not-All-Equal (NAE) solutions of Hamming weight exactly t(n), i.e., those that satisfy and falsify some literal in every clause. We refine the algorithm of Gurumukhani et al. and show that it optimally solves NAE-Enum(3, n/2), namely, in expected time poly(n) ⋅ 6^{n/4}.
Cite as

Mohit Gurumukhani, Ramamohan Paturi, Michael Saks, and Navid Talebanfard. Local Enumeration: The Not-All-Equal Case. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gurumukhani_et_al:LIPIcs.STACS.2025.42,
  author =	{Gurumukhani, Mohit and Paturi, Ramamohan and Saks, Michael and Talebanfard, Navid},
  title =	{{Local Enumeration: The Not-All-Equal Case}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.42},
  URN =		{urn:nbn:de:0030-drops-228680},
  doi =		{10.4230/LIPIcs.STACS.2025.42},
  annote =	{Keywords: Depth 3 circuits, k-CNF satisfiability, Circuit lower bounds, Majority function}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.7
Depth-Three Circuits for Inner Product and Majority Functions

Authors: Kazuyuki Amano

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
We consider the complexity of depth-three Boolean circuits with limited bottom fan-in that compute some explicit functions. This is one of the simplest circuit classes for which we cannot derive tight bounds on the complexity for many functions. A Σ₃^k-circuit is a depth-three OR ∘ AND ∘ OR circuit in which each bottom gate has fan-in at most k. First, we investigate the complexity of Σ₃^k-circuits computing the inner product mod two function IP_n on n pairs of variables for small values of k. We give an explicit construction of a Σ²₃-circuit of size smaller than 2^{0.952n} for IP_n as well as a Σ³₃-circuit of size smaller than 2^{0.692n}. These improve the known upper bounds of 2^{n-o(n)} for Σ₃²-circuits and 3^{n/2} ∼ 2^{0.792n} for Σ₃³-circuits by Golovnev, Kulikov and Williams (ITCS 2021), and also the upper bound of 2^{(0.965…)n} for Σ₃²-circuits shown in a recent concurrent work by Göös, Guan and Mosnoi (MFCS 2023). Second, we investigate the complexity of the majority function MAJ_n aiming for exploring the effect of negations. Currently, the smallest known depth-three circuit for MAJ_n is a monotone circuit. A Σ₃^{(+k,-𝓁)}-circuit is a Σ₃-circuit in which each bottom gate has at most k positive literals and 𝓁 negative literals as its input. We show that, for k ≤ 2, the minimum size of a Σ₃^{(+k,-∞)}-circuit for MAJ_n is essentially equal to the minimum size of a monotone Σ₃^k-circuit for MAJ_n. In sharp contrast, we also show that, for k = 3,4 and 5, there exists a Σ₃^{(+k, -𝓁)}-circuit computing MAJ_n (for an appropriately chosen 𝓁) that is smaller than the smallest known monotone Σ₃^k-circuit for MAJ_n. Our results suggest that negations may help to speed up the computation of the majority function even for depth-three circuits. All these constructions rely on efficient circuits or formulas on a small number of variables that we found through a computer search.
Cite as

Kazuyuki Amano. Depth-Three Circuits for Inner Product and Majority Functions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{amano:LIPIcs.ISAAC.2023.7,
  author =	{Amano, Kazuyuki},
  title =	{{Depth-Three Circuits for Inner Product and Majority Functions}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.7},
  URN =		{urn:nbn:de:0030-drops-193092},
  doi =		{10.4230/LIPIcs.ISAAC.2023.7},
  annote =	{Keywords: Circuit complexity, depth-3 circuits, upper bounds, lower bounds, computer-assisted proof}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.29
Integer Complexity and Mixed Binary-Ternary Representation

Authors: Kazuyuki Amano

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
The integer complexity of a natural number n, denoted by ‖n‖, is the smallest number of 1’s needed to express n using an arbitrary combination of addition and multiplication (and parentheses). For example, ‖6‖ = 5 since the expression 6 = (1+1)⋅ (1+1+1) contains five 1’s and there are no such expressions containing at most four 1’s. The investigation of this cute complexity measure was originated by Mahler and Popken in the 1950s. It is easy to see that ‖n‖/(log₃ n) ∈ [3, 3 log₂ 3] (∼ [3,4.755]) for every n, but the distribution of ‖n‖ is largely unknown. In this work, we focus on the restricted expressions obtained by applying Horner’s schema to a mixed binary-ternary representation of a given number in which we can arrange base-two and base-three digits in an arbitrary order. Let f(n) denote the minimum number of 1’s needed to express n in this way. Apparently, f(n) ≥ ‖n‖ for every n. We extensively investigate on f(n) via the combination of computer experiments and theoretical analysis and obtain the following set of results: (i) Computer experiments supporting the hypothesis that f(n)/log₃ n < 3.483 on average and f(n)/log₃ n < 4.212 for all n, (ii) For almost all natural numbers n, 3.120 < f(n)/log₃ n < 3.587, and (iii) There are infinitely many n’s such that f(n)/log₃ n > 3.934. Several new bounds on the original integer complexity are also presented in the paper.
Cite as

Kazuyuki Amano. Integer Complexity and Mixed Binary-Ternary Representation. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{amano:LIPIcs.ISAAC.2022.29,
  author =	{Amano, Kazuyuki},
  title =	{{Integer Complexity and Mixed Binary-Ternary Representation}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.29},
  URN =		{urn:nbn:de:0030-drops-173146},
  doi =		{10.4230/LIPIcs.ISAAC.2022.29},
  annote =	{Keywords: Integer complexity, Lower bounds, Upper bounds, Horner’s schema, Computer assisted proof}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.81
Depth Two Majority Circuits for Majority and List Expanders

Authors: Kazuyuki Amano

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Let MAJ_n denote the Boolean majority function of n input variables. In this paper, we study the construction of depth two circuits computing MAJ_n where each gate in a circuit computes MAJ_m for m < n. We first give an explicit construction of depth two MAJ_{floor[n/2]+2} o MAJ_{<= n-2} circuits computing MAJ_n for every n >= 7 such that n congruent 3 (mod 4) where MAJ_m and MAJ_{<= m} denote the majority gates that take m and at most m distinct inputs, respectively. A graph theoretic argument developed by Kulikov and Podolskii (STACS '17, Article No. 49) shows that there is no MAJ_{<= n-2} o MAJ_{n-2} circuit computing MAJ_n. Hence, our construction reveals that the use of a smaller fan-in gates at the bottom level is essential for the existence of such a circuit. Some computational results are also provided. We then show that the construction of depth two MAJ_m o MAJ_m circuits computing MAJ_n for m<n can be translated into the construction of a newly introduced version of bipartite expander graphs which we call a list expander. Intuitively, a list expander is a c-leftregular bipartite graph such that for a given d < c, every d-leftregular subgraph of the original graph has a certain expansion property. We formalize this connection and verify that, with high probability, a random bipartite graph is a list expander of certain parameters. However, the parameters obtained are not sufficient to give us a MAJ_{n-c} o MAJ_{n-c} circuit computing MAJ_n for a large constant c.
Cite as

Kazuyuki Amano. Depth Two Majority Circuits for Majority and List Expanders. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{amano:LIPIcs.MFCS.2018.81,
  author =	{Amano, Kazuyuki},
  title =	{{Depth Two Majority Circuits for Majority and List Expanders}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{81:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.81},
  URN =		{urn:nbn:de:0030-drops-96633},
  doi =		{10.4230/LIPIcs.MFCS.2018.81},
  annote =	{Keywords: Boolean function, majority function, constant depth circuit, expander graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.5
On the Number of p4-Tilings by an n-Omino

Authors: Kazuyuki Amano and Yoshinobu Haruyama

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
A plane tiling by the copies of a polyomino is called isohedral if every pair of copies in the tiling has a symmetry of the tiling that maps one copy to the other. We show that, for every $n$-omino (i.e., polyomino consisting of n cells), the number of non-equivalent isohedral tilings generated by 90 degree rotations, so called p4-tilings or quarter-turn tilings, is bounded by a constant (independent of n). The proof relies on the analysis of the factorization of the boundary word of a polyomino.
Cite as

Kazuyuki Amano and Yoshinobu Haruyama. On the Number of p4-Tilings by an n-Omino. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{amano_et_al:LIPIcs.ISAAC.2017.5,
  author =	{Amano, Kazuyuki and Haruyama, Yoshinobu},
  title =	{{On the Number of p4-Tilings by an n-Omino}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.5},
  URN =		{urn:nbn:de:0030-drops-82498},
  doi =		{10.4230/LIPIcs.ISAAC.2017.5},
  annote =	{Keywords: polyomino, plane tiling, isohedral tiling, word factorization}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2023
  • 1 2022
  • 1 2018
  • Show More...

  • Refine by Author
  • 4 Amano, Kazuyuki
  • 1 Carmosino, Marco
  • 1 Dang, Ngu
  • 1 Gurumukhani, Mohit
  • 1 Haruyama, Yoshinobu
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Circuit complexity
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Proof complexity

  • Refine by Keyword
  • 1 Boolean function
  • 1 Circuit Lower Bounds
  • 1 Circuit complexity
  • 1 Circuit lower bounds
  • 1 Computer assisted proof
  • 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