Category: Research

Running experiments on AWS

I can’t say how happy I am to have AWS. I just got the account set up, started my first instance, and run a simulation for a very interesting project that I am working on with Ryan McIntyre (a student in CS). What took about 15min on my Mac Pro quad core, took 1m40s on the AWS instance.

This is a brave new world! 🙂 . Here us the summary of the experiment:

~/EdgeGraph/EdgeGraph$ time python3 cover_vs_edges.py 
How many vertices? 7
Generating graphs...
Filtering isomorphisms...
Sorting graphs...
Checking up to 21 edges...
0 / 21 edges complete.
1 / 21 edges complete.
2 / 21 edges complete.
3 / 21 edges complete.
4 / 21 edges complete.
5 / 21 edges complete.
6 / 21 edges complete.
7 / 21 edges complete.
8 / 21 edges complete.
9 / 21 edges complete.
10 / 21 edges complete.
11 / 21 edges complete.
12 / 21 edges complete.
13 / 21 edges complete.
14 / 21 edges complete.
15 / 21 edges complete.
16 / 21 edges complete.
17 / 21 edges complete.
18 / 21 edges complete.
19 / 21 edges complete.
20 / 21 edges complete.
21 / 21 edges complete.
elapsed time: --- 96.4 seconds ---

real 1m40.000s
user 1m36.812s
sys 0m0.113s

Rabin Miller algorithm: witnesses of compositness

The Rabin Miller algorithm for primality testing relies on a random selection of a’s for which it performs some basic tests in order to determine whether the input n is prime or composite. If n is prime, all a’s work, but if n is composite it is possible to show that at least half of the a’s work, i.e., at least half of the a’s are witnesses of compositness. But in fact, it seems like a lot more a’s than just half of those in the set {1,2,…,n-1} work; see the following diagram where I test all composites under about 60,000. It is clear that there are more good witnesses than just half the numbers.

plot-witnesses

Square-free strings over alphabet lists

In a new paper, Square-free strings over alphabet lists, my PhD student Neerja Mhaskar and I, solve an open problem that was posed in A new approach to non repetitive sequences, by Jaroslaw Grytczuk, Jakub Kozik, and Pitor Micek, in arXiv:1103.3809, December 2010.

The problem can be stated as follows: Given an alphabet list $L=L_1,\ldots,L_n$, where $|L_i|=3$ and $0 \leq i \leq n$, can we always find a square-free string, $W=W_1W_2 \ldots W_n$, where $W_i\in L_i$? We show that this is indeed the case. We do so using an “offending suffix” characterization of forced repetitions, and a counting, non-constructive, technique. We discuss future directions related to finding a constructive solution, namely a polytime algorithm for generating square-free words over such lists.

Our paper will be presented and published in the 26th International Workshop on Combinatorial Algorithms (IWOCA), Verona, Italy, October 2015.

My work on finite games cited by researchers at Vienna school of Economics

I wrote a paper about finite games which I presented at Computability in Europe in Athens, 2009. Now it turns out, that the Vienna school of Economics, Wirtschaftsuniversität Wien, has been citing it repeatedly in the last few months, in particular Aurélien Fichet de Clairfontaine. It is very satisfying to see research being picked up by other areas!

A new paper: Non-repetitive strings, with Neerja Mhaskar

Title: Non-repetitive strings over alphabet lists

Authors: Neerja Mhaskar and Michael Soltys

Abstract: A word is non-repetitive if it does not contain a subword of the form vv. Given a list of alphabets L = L1, L2, . . . , Ln, we investigate the question of generating non-repetitive words w = w1w2 . . . wn, such that the symbol wi is a letter in the alphabet Li. This problem has been studied by several authors (e.g., [GKM10], [Sha09]), and it is a natural extension of the original problem posed and solved by A. Thue. While we do not solve the problem in its full generality, we show that such strings exist over many classes of lists. We also suggest techniques for tackling the problem, ranging from online algorithms, to combinatorics over 0-1 matrices, and to proof complexity. Finally, we show some properties of the extension of the problem to abelian squares.

Source:

A new paper: String Shuffle, with Neerja Mhaskar

Title: String Shuffle: Circuits and Graphs

Authors: Neerja Mhaskar and Michael Soltys

Abstract: We show that shuffle, the problem of determining whether a string w can be composed from an order preserving shuffle of strings x and y, is not in AC0, but it is in AC1. The fact that shuffle is not in AC0 is shown by a reduction of parity to shuffle and invoking the seminal result of Furst et al., while the fact that it is in AC1 is implicit in the results of Mansfield. Together, the two results provide a lower and upper bound on the complexity of this combinatorial problem. We also explore an interesting relationship between graphs and the shuffle problem, namely what types of graphs can be represented with strings exhibiting the anti-Monge condition.

Source:

UC Santa Barbara students, staff jubilant after professor’s Nobel Prize win

Students and staff at UC Santa Barbara were delighted Tuesday after learning that one of their professors had been awarded a Nobel Prize in physics.

They said it would boost the campus’ academic standing and help them shed their collective grief over last spring’s deadly off-campus shooting in Isla Vista.

Shuji Nakamura, a professor of materials and of electrical and computer engineering at UC Santa Barbara, was named a co-winner with two Japanese scientists for devising a blue light-emitting diode that paved the way for energy-efficient LED lighting.

via UC Santa Barbara students, staff jubilant after professor’s Nobel Prize win – LA Times.

Ariel Fernández Ph.D.

My Ph.D. student, Ariel Fernández, has successfully defended his thesis on June 10, 2013: Formalizing Combinatorial Matrix Theory.

The results of that thesis were presented at two conferences:

How hard in unshuffling a square?

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI. Lets call a string a square if it is a shuffle of two identical strings.

In November 2012, Sam Buss and I have succeeded in proving that the problem of determining whether a string can be written as a square shuffle is NP complete. This applies even over a finite alphabet with only 7 distinct symbols, although our proof is written for an alphabet with 9 symbols. This question is still open for smaller alphabets, say with only 2 symbols.

This problem was first posted on the CS Theory Community Blog in August of 2010. The problem received a lot of attention at the Theoretical Computer Science StackExchange. Our solution has been published in December 2013, the Journal of Computer and System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

(here is the corresponding StackExchange post)