Browse Proceedings

This talk presents the author's personal favorites of fun talks from algorithms and complexity. Not all of these were presented at FUN, but definitely would have generated fun at FUN.

We discuss two different ways of having fun with two different kinds of games: On the one hand, we present a framework for developing multiplayer pervasive games that rely on the use of mobile sensor networks. On the other hand, we show how to exploit ...

Removing noises in a given binary image is one of common operations. A generalization of the operation is to erase arbitrarily specified component by reversing pixels values in the component. This paper shows that this operation is done without using ...

Kaboozle is a puzzle consisting of several square cards, each annotated with colored paths and dots drawn on both sides and holes drilled. The goal is to join two colored dots with paths of the same color (and fill all holes) by stacking the cards ...

Consider the following game. There are n players, each wearing a hat colored red or blue. Each player does not see the color of her own hat but does see the colors of all other hats. Simultaneously, each player has to guess the color of her own hat, ...

In this paper we introduce new algebraic forms, SOP+ and DSOP+, to represent functions f : {0,1}ⁿ → N, based on arithmetic sums of products. These expressions are a direct generalization of the classical SOP and DSOP forms. We propose optimal and ...

Sending text messages on cell phones which only contain the keys 0 through 9 and # and * can be a painful experience. We consider the problem of designing an optimal mapping of numbers to sets of letters to act as an alternative to the standard {2 → {...

You are an urban hitchhiker. All drivers are willing to give you a ride, as long as they do not have to alter their trajectories to accommodate your needs. How (and how quickly) can you get to your destination? We analyze two scenarios, depending on ...

The way memory hierarchy has evolved in recent decades has opened new challenges in the development of indexing structures in general and spatial access methods in particular. In this paper we propose an original approach to represent geographic data ...

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of Parikh vector q (a "jumbled string") in the text s requires to find a substring t of s with p(t) = q. The corresponding ...

Gradwohl et al. (2007) gave a zero-knowledge proof for Sudoku that can be implemented physically using common tools like envelopes and bags, and the procedures are so simple that they can be executed solely by kids. In this paper, we work along with ...

Suppose we have a set of materials -- e.g., drugs or genes -- some combinations of which react badly together. We can experiment to see whether subsets contain any bad combinations and we want to find a maximal subset that does not. This problem is ...

We consider a variant of the graph searching games that is closely related to the routing reconfiguration problem in WDM networks. In the digraph processing game, a team of agents is aiming at clearing, or processing, the vertices of a digraph D. In ...

UNO® is one of the world-wide well-known and popular card games. We investigate UNO from the viewpoint of combinatorial algorithmic game theory by giving some simple and concise mathematical models for it. They include cooperative and uncooperative ...

We propose a model for level-ups in Heroes of Might and Magic III, and give an O(1/ε² ln (1/δ)) learning algorithm to estimate the probabilities of secondary skills induced by any policy in the end of the leveling-up process. We develop software and ...

We introduce a new number system that supports increments with a constant number of digit changes. We also give a simple method that extends any number system supporting increments to support decrements using the same number of digit changes. In the new ...

We investigate the problem of getting to a higher instruction-level parallelism in string matching algorithms. In particular, starting from an algorithm based on bit-parallelism, we propose two flexible approaches for boosting it with a higher level of ...

The HONEY-BEE game is a two-player board game that is played on a connected hexagonal colored grid, or in a generalized setting, on a connected graph with colored nodes. In a single move, a player calls a color and thereby conquers all nodes of that ...

We consider a class of highly dynamic networks modelled on an urban subway system. We examine the problem of creating a map of such a subway in less than ideal conditions, where the local residents are not enthusiastic about the process and there is a ...

The bank director was pretty upset noticing Joe, the system administrator, spending his spare time playing Mastermind, an old useless game of the 70ies. He had fought the instinct of telling him how to better spend his life, just limiting to look at him ...

We analyze the computational complexity of various two-dimensional platform games. We state and prove several meta-theorems that identify a class of these games for which the set of solvable levels is NP-hard, and another class for which the set is even ...

The Christmas gift exchange is a popular party game played around Christmas. Each participant brings a Christmas present to the party, and a random ordering of the participants, according to which they will choose gifts, is announced. When a participant'...

We follow the travails of Enzo the baker, Orsino the oven man, and Beppe the planner. Their situation have a common theme: They know the input, in the form of a sequence of items, and they are not computationally constrained. Their issue is that they ...

In spite of futurologists' best predictions change has not gone away, and it is probably prudent that we not expect this to change any time soon. In this paper we consider the challenges of change, particularly in today's era of smartphones. We consider ...

Martin Gardner in the early 1970's described the game of RaceTrack [M. Gardner, Mathematical games--Sim, Chomp and Race Track: new games for the intellect (and not for Lady Luck), Scientific American, 228(1):108-115, Jan. 1973]. Here we study the ...

We prove that it is NP-hard to decide whether two points in a polygonal domain with holes can be connected by a wire. This implies that finding any approximation to the shortest path for a long snake amidst polygonal obstacles is NP-hard. On the ...

A man walks into a men's room and observes n empty urinals. Which urinal should he pick so as to maximize his chances of maintaining privacy, i.e., minimize the chance that someone will occupy a urinal beside him? In this paper, we attempt to answer ...

In countries such as China or Iran where Internet censorship is prevalent, users usually rely on proxies or anonymizers to freely access the web. The obvious difficulty with this approach is that once the address of a proxy or an anonymizer is announced ...

We study the complexity of the popular one player combinatorial game known as Flood-It. In this game the player is given an n×n board of tiles, each of which is allocated one of c colours. The goal is to fill the whole board with the same colour via the ...