Source author record

Suthee Ruangwises

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Cryptography and Security Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

4works

3topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

NP-Completeness Proofs of Puzzles using the T-Metacell Framework

Pencil puzzles are puzzles that can be solved by writing down solutions on a paper, using only logical reasoning. In this paper, we utilize the "T-metacell" framework developed by Tang and the MIT Hardness Group to prove the NP-completeness of four new pencil puzzles: Grand Tour, Entry Exit, Zahlenschlange, and Yagit. Additionally, the first three are also proven to be ASP-complete. The results demonstrate how versatile the framework is, offering new insights into the computational complexity of problems with various constraints.

preprint2022arXiv

Physical ZKP for Makaro Using a Standard Deck of Cards

Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a prover to physically convince a verifier that he/she knows a solution of the puzzle without revealing it. However, their protocol requires several identical copies of some cards, making it impractical as a deck of playing cards found in everyday life typically consists of all different cards. In this paper, we propose a new ZKP protocol for Makaro that can be implemented using a standard deck (a deck consisting of all different cards). Our protocol also uses asymptotically less cards than the protocol of Bultel et al. Most importantly, we develop a general method to encode a number with a sequence of all different cards. This allows us to securely compute several numerical functions using a standard deck, such as verifying that two given numbers are different and verifying that a number is the largest one among the given numbers.

preprint2022arXiv

Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku

Sudoku is a famous logic puzzle where the player has to fill a number between 1 and 9 into each empty cell of a $9 \times 9$ grid such that every number appears exactly once in each row, each column, and each $3 \times 3$ block. In 2020, Sasaki et al. developed a physical card-based protocol of zero-knowledge proof (ZKP) for Sudoku, which enables a prover to convince a verifier that he/she knows a solution of the puzzle without revealing it. Their protocol uses 90 cards, but requires nine identical copies of some cards, which cannot be found in a standard deck of playing cards (consisting of 52 different cards and two jokers). Hence, nine identical standard decks are required to perform that protocol, making the protocol not very practical. In this paper, we propose a new ZKP protocol for Sudoku that can be performed using only two standard decks of playing cards, regardless of whether the two decks are identical or different. In general, we also develop the first ZKP protocol for a generalized $n \times n$ Sudoku that can be performed using a deck of all different cards.

preprint2016arXiv

Random Almost-Popular Matchings

For a set $A$ of $n$ people and a set $B$ of $m$ items, with each person having a preference list that ranks all items from most wanted to least wanted, we consider the problem of matching every person with a unique item. A matching $M$ is called $ε$ -popular if for any other matching $M'$ , the number of people who prefer $M'$ to $M$ is at most $εn$ plus the number of those who prefer $M$ to $M'$ . In 2006, Mahdian showed that when randomly generating people's preference lists, if $m/n > 1.42$ , then a 0-popular matching exists with $1-o(1)$ probability; and if $m/n < 1.42$ , then a 0-popular matching exists with $o(1)$ probability. The ratio 1.42 can be viewed as a transition point, at which the probability rises from asymptotically zero to asymptotically one, for the case $ε=0$ . In this paper, we introduce an upper bound and a lower bound of the transition point in more general cases. In particular, we show that when randomly generating each person's preference list, if $α(1-e^{-1/α}) > 1-ε$ , then an $ε$ -popular matching exists with $1-o(1)$ probability (upper bound); and if $α(1-e^{-(1+e^{1/α})/α}) < 1-2ε$ , then an $ε$ -popular matching exists with $o(1)$ probability (lower bound).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.