Continue reading 11th Int’l Conference on Computability, Complexity and Randomness 2016
Category Archives: conferences
Humuhumunukunukuapua’a at the Symposium
2nd Annual SURE Symposium 2019
SURE: Summer Undergraduate Research Experience
will feature two projects mentored by Prof. Kjos-Hanssen:
VC-dimensions of nondeterministic finite automata for words of equal length
Davin Takahashi and Ethan Lamb
Ishigami and Tani studied VC-dimensions of finite automata. We show that their results apply to a new notion, lower VC-dimension, where all sets (instead of some set) of a given cardinality must be shattered. We also relate the VC-dimension to the Separating Words problem.
Savings from word powers in automatic complexity
Sun Young Kim and Clyde Felix
The automatic complexity of a word was introduced by Shallit and Wang in 2001 and studied further by Kjos-Hanssen since 2013. In this work we develop an implementation of a lower bound on the complexity involving occurrences of powers of words, such as the occurrence of “humu” twice in “humuhumunukunukuapua’a”.
Extracting randomness within a subset
Shift registers fool finite automata @ WoLLIC and in Discrete Mathematics
LFSRs (linear feedback shift registers) are popular pseudorandomness generators.
In a new project we show that they generate output (often called $m$-sequences) of maximal (nondeterministic path-based) automatic complexity. At this point we have an experimental result, one which would have probability $2^{-93}$ to occur “by chance”, as well as a theoretical but sub-optimal result.
Moreover, an $m$-sequence of length 31 provides an example of a word $x$ such that
$$
A^-(x)=A_N(x)+2
$$
where $A_N$ is nondeterministic path-based automatic complexity, and $A^-$ is non-total deterministic automatic complexity.
Such an example (where $A^-(x)-A_N(x)>1$) was not known before the consideration of LFSRs in this area. That consideration was an idea of Jason Castiglione.
The paper has been accepted at WoLLIC 2017 and in journal form for Discrete Mathematics (2018).
This project was presented at the poster session of the SIAM Conference on Discrete Mathematics 2016 in Atlanta, Georgia. The session was otherwise dominated by interesting work on RNA pseudoknots and chord diagrams (3 out of 6 posters) which in the case of the work of the Biocomplexity Institute researchers Ricky Chen and Thomas Li involves modeling with multiply context-free grammars.
Superposition as memory @ UCNC17
Imagine a lock with two states, locked and unlocked, which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four operations is to do them in the sequence 0011, i.e., $0^n1^n$ where $n=2$. In this scenario one might think that the lock needs to be in certain further states after each operation, so that there is some memory of what has been done so far. Here we show that this memory can be entirely encoded in superpositions of the two basic states locked and unlocked, where, as dictated by quantum mechanics, the operations are given by unitary matrices. Moreover, we show using the Jordan–Schur lemma that a similar lock is not possible for $n=60$.
Details in the paper: Superposition as memory: unlocking quantum automatic complexity which appeared in the Lecture Notes in Computer Science volume of the conference Unconventional Computation and Natural Computation (UCNC) 2017.
ASL Annual Meetings in North America
| Midwest $n-2$ | East $n-1$ | West $n$ | $n$ |
|---|---|---|---|
| Western Illinois | 2020 | ||
| UIUC | UConn | Boise State | 2017 |
| UW Madison | Waterloo, ON | UC Boulder | 2014 |
| Notre Dame | Washington, D.C.** | UC Berkeley | 2011 |
| Montreál, QC | U. Florida* | UC Irvine* | 2008 |
| UIC | Carnegie Mellon | Stanford* | 2005 |
| UIUC | U. Pennsylvania | Las Vegas | 2002 |
**invited plenary speaker
*special session speaker
attendee
Covering the computable sets
I participated in the workshop on Algorithmic Randomness in Singapore and the conference on Computability, Complexity and Randomness.
With host Frank Stephan and fellow participant Sebastiaan Terwijn we wrote a paper entitled Covering the recursive sets which appeared in Lecture Notes in Computer Science, Conference on Computability in Europe, 2015, and has now been published in Annals of Pure and Applied Logic.
Interactions between computability, universal algebra, and group theory
All talks will be in Keller Hall 314.
Scientific program
Thursday February 12
- 10:30-11:20am Olga Kharlampovich (CUNY — Hunter College): Elementary classification questions for groups and algebras I: Groups.
- 11:30am-1:20pm: CASUAL LUNCH. Suggestion: Manoa Gardens
- 1:30-2:20pm Free discussion
Friday February 13
- 9:30-10:20am Bakhadyr Khoussainov (University of Auckland):A quest for algorithmically random algebraic structures
- 11:30-12:20pm Alexei Miasnikov (Stevens Institute of Technology): Elementary classification questions for groups and algebras II: Associative and Lie algebras.
- 12:30-1:20pm BRIEF LUNCH. Suggestion: Sustainability Courtyard
- 1:30-2:20pm Paul Kim Long V. Nguyen (University of Hawaii — Leeward Community College): $\Sigma^0_3$-completeness of subdirect irreducibility
Abstract (Kharlampovich and Miasnikov)
We consider some fundamental model-theoretic questions that can be asked about a given algebraic structure (a group, a ring, etc.), or a class of structures, to understand its principal algebraic and logical properties. These Tarski type questions include: elementary classification and decidability of the first-order theory.
In the case of free groups we proved that two non-abelian free groups of different ranks are elementarily equivalent, classified finitely generated groups elementarily equivalent to a finitely generated free group (also done by Sela) and proved decidability of the first-order theory.
We describe partial solutions to Tarski’s problems in the class of free associative and Lie algebras of finite rank and some open problems. In particular, we will show that unlike free groups, two free associative algebras of finite rank over the same field are elementarily equivalent if and only if they are isomorphic. Two free associative algebras of finite rank over different infinite fields are elementarily equivalent if and only if the fields are equivalent in the weak second order logic, and the ranks are the same. We will also show that for an infinite field the theory of a free associative algebra is undecidable.
Things to do in Honolulu
Pow!Wow! art festival
Travel: parking, getting to campus from your hotel, and beaches.