Kazuyuki Amano

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., September, 2023

Depth-Three Circuits for Inner Product and Majority Functions.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022

Integer Complexity and Mixed Binary-Ternary Representation.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Escape from the Room.

[BibT_eX]

[DOI]

Kento Kimura

Proceedings of the Computing and Combinatorics - 28th International Conference, 2022

2021

On the Minimum Number of Pieces for Two-Dimensional Anti-Slide Using T-Tetrominoes.

[BibT_eX]

[DOI]

Kento Kimura

Tetsuya Araki

IEICE Trans. Inf. Syst., 2021

Maximum Number of Steps of Topswops on 18 and 19 Cards.

[BibT_eX]

[DOI]

CoRR, 2021

2020

An Approximation Algorithm for the 2-Dispersion Problem.

[BibT_eX]

[DOI]

IEICE Trans. Inf. Syst., 2020

Search for developments of a box having multiple ways of folding by SAT solver.

[BibT_eX]

[DOI]

Riona Tadaki

CoRR, 2020

On the Size of Depth-Two Threshold Circuits for the Inner Product Mod 2 Function.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2020

2019

On the Number of p4-Tilings by an n-Omino.

[BibT_eX]

[DOI]

Yoshinobu Haruyama

Int. J. Comput. Geom. Appl., 2019

On XOR lemmas for the weight of polynomial threshold functions.

[BibT_eX]

[DOI]

Shoma Tate

Inf. Comput., 2019

2018

Depth Two (n-2)-Majority Circuits for n-Majority.

[BibT_eX]

[DOI]

Masafumi Yoshida

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2018

Depth Two Majority Circuits for Majority and List Expanders.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Away from Rivals.

[BibT_eX]

[DOI]

Proceedings of the 30th Canadian Conference on Computational Geometry, 2018

2017

Enumeration of Boolean functions of sensitivity three and inheritance of nondegeneracy.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

2016

On XOR Lemma for Polynomial Threshold Weight and Length.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2016

2015

Anti-Slide.

[BibT_eX]

[DOI]

Koichi Yamazaki

J. Inf. Process., 2015

A Satisfiability Algorithm for Some Class of Dense Depth Two Threshold Circuits.

[BibT_eX]

[DOI]

Atsushi Saito

IEICE Trans. Inf. Syst., 2015

Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds.

[BibT_eX]

[DOI]

IEICE Trans. Inf. Syst., 2015

Ordered biclique partitions and communication complexity problems.

[BibT_eX]

[DOI]

Manami Shigeta

Discret. Appl. Math., 2015

A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP.

[BibT_eX]

[DOI]

Atsushi Saito

Proceedings of the Language and Automata Theory and Applications, 2015

2014

Foreword.

[BibT_eX]

[DOI]

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2014

On extremal kk-CNF formulas.

[BibT_eX]

[DOI]

Eur. J. Comb., 2014

Some improved bounds on communication complexity via new decomposition of cliques.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2014

2012

How to Solve the Torus Puzzle.

[BibT_eX]

[DOI]

Algorithms, 2012

2011

Tight Bounds on the Average Sensitivity of k-CNF.

[BibT_eX]

[DOI]

Theory Comput., 2011

A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds.

[BibT_eX]

[DOI]

Jun Tarui

Theor. Comput. Sci., 2011

Minterm-transitive functions with asymptotically smallest block sensitivity.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

On Extremal k-CNF Formulas.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2011

On Directional vs. General Randomized Decision Tree Complexity for Read-Once Formulas.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2011

Bounding the Randomized Decision Tree Complexity of Read-Once Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

NPN-Representatives of a Set of Optimal Boolean Formulas.

[BibT_eX]

[DOI]

Hideaki Fukuhara

Eiji Takimoto

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2010

Researching the Complexity of Boolean Functions with Computers.

[BibT_eX]

[DOI]

Bull. EATCS, 2010

k-Subgraph Isomorphism on AC0 Circuits.

[BibT_eX]

[DOI]

Comput. Complex., 2010

New Upper Bounds on the Average PTF Density of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

On Directional vs. Undirectional Randomized Decision Tree Complexity for Read-Once Formulas.

[BibT_eX]

[DOI]

Proceedings of the Theory of Computing 2010, 2010

2009

A Note on the Middle Levels Conjecture

[BibT_eX]

[DOI]

Manabu Shimada

CoRR, 2009

Bounds on the Size of Small Depth Circuits for Approximating Majority.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

k-Subgraph Isomorphism on AC0 Circuits.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds.

[BibT_eX]

[DOI]

Jun Tarui

Proceedings of the Theory and Applications of Models of Computation, 2008

Monotone DNF Formula That Has a Minimal or Maximal Number of Satisfying Assignments.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

2007

Better upper bounds on the QOBDD size of integer multiplication.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

2006

On learning monotone Boolean functions under the uniform distribution.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

The Monotone Circuit Complexity of Quadratic Boolean Functions.

[BibT_eX]

[DOI]

Algorithmica, 2006

On the Negation-Limited Circuit Complexity of Sorting and Inverting k-tonic Sequences.

[BibT_eX]

[DOI]

Takayuki Sato

Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

2005

A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

On the Complexity of Depth-2 Circuits with Threshold Gates.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2004

The Potential of the Approximation Method.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Better Simulation of Exponential Threshold Weights by Polynomial Weights

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

2003

Inclusion-exclusion for k-CNF formulas.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

On the negation-limited circuit complexity of merging.

[BibT_eX]

[DOI]

Jun Tarui

Discret. Appl. Math., 2003

On Optimal Merging Networks.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Some Properties of MODm Circuits Computing Simple Functions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2001

On a Generalized Ruin Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

The Computational Power of a Family of Decision Forests.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

2000

On-Line Estimation of Hidden Markov Model Parameters.

[BibT_eX]

[DOI]

Proceedings of the Discovery Science, 2000

1997

Approximation Algorithms for DNF Under Distributions with Limited Independence.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1997

1996

Potential of the Approximation Method (extended abstract).

[BibT_eX]

[DOI]