Contact
Office: 306 Keller Hall
Office hours: M 1:00pm-2:00pm
W 1:00pm-2:00pm
F 11:30am-12:30pm
Email: beros@math.hawaii.edu
Publications
(Submitted for Publication)
A. Beros and K Beros
We examine sets of codes such that certain properties are invariant under the choice of oracle from a range of possible oracles and establish a connection between such codes and Medvedev reductions. In examing the complexity of such sets of \emph{universal codes}, we prove completeness results at various levels of the arithmetic hierarchy as well as two general theorems for obtaining Π11-completeness for sets of universal codes. Among other corollaries, we show that the set of codes for Medvedev reductions of bi-immune sets to DNC functions is Π11-complete.
Classifying the Arithmetical Complexity of Teaching Models
(To appear in the proceedings of Algorithmic Learning Theory (ALT) 2016)
A. Beros, Z. Gao, S. Zilles
This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the index sets of the following classes: (1) the class of uniformly r.e. families with finite teaching dimension, and (2) the class of uniformly r.e. families with finite positive recursive teaching dimension witnessed by a uniformly r.e. teaching sequence. We also derive the arithmetical complexity of several other decision problems in teaching.
Effective Bi-Immunity and Randomness
(To appear in the proceedings of Computability and Complexity Symposium 2017)
A. Beros, M. Khan and B. Kjos-Hansen
We study the relationship between randomness and effective bi-immunity. Greenberg and Miller have shown that for any oracle X, there are arbitrarily slow-growing DNR functions relative to X that compute no ML random set. We show that the same holds when ML randomness is replaced with effective bi-immunity. It follows that there are sequences of effective Hausdorff dimension 1 that compute no effectively bi-immune set.
We also establish an important difference between the two properties. The class Low(MLR, EBI) of oracles relative to which every ML random is effectively bi-immune contains the jump-traceable sets, and is therefore of cardinality continuum.
(Submitted for Publication)
A. Beros and C. de la Higuera
We compare the efficiency of learning using a membership oracle and learning using a teacher. We find that there is a large class of families for which the teacher provides a super-exponential efficiency gain over learning with an oracle. Furthermore, using both a teacher and an oracle provides a super-exponential gain over either learning with only an oracle and learning with only a teacher.
(To Appear in Fundamenta Informaticae)
A. Beros and C. de la Higuera
We prove the existence of a canonical form for semi-deterministic transducers with incomparable sets of output strings. Based on this, we develop an algorithm which learns semi-deterministic transducers given access to translation queries. We also prove that there is no learning algorithm for semi-deterministic transducers that uses only domain knowledge.
(JMLR W&CP 34 :33-48, 2014)
A. Beros and C. de la Higuera
We prove the existence of a canonical form for semi-deterministic transducers with incomparable sets of output strings. Based on this, we develop an algorithm which learns semi-deterministic transducers given access to translation queries. We also prove that there is no learning algorithm for semi-deterministic transducers that uses only domain knowledge.
(To Appear in the Notre Dame Journal of Formal Logic)
A. Beros and K. Beros
Given any oracle, A, we construct a basic sequence Q, computable in the jump of A, such that no A-computable real is Q-distribution-normal. A corollary to this is that there is a Δ0n+1 basic sequence with respect to which no Δ0n real is distribution-normal. As a special case, there is a limit computable sequence relative to which no computable real is distribution-normal.
(Archive for Mathematical Logic, 54(5):521--530, 2015)
A. Beros
In Diagonally Non-Computable Functions and Bi-Immunity, Carl Jockusch and Andrew Lewis proved that every DNC function computes a bi-immune set. They asked whether every DNC function computes an effectively bi-immune set. We construct a DNC function that computes no effectively bi-immune set, thereby answering their question in the negative.
(Journal of Symbolic Logic, 78(4):1183--1188, 2013)
A. Beros
In 1986, Osherson, Stob and Weinstein asked whether two variants of anomalous vacillatory learning, TxtFex** and TxtFext**, could be distinguished. These learning criteria place bounds neither on the number of hypotheses between which the learner is allowed to vacillate nor on the number of errors permitted, merely that both are finite. The criteria differ in that the more restrictive one, TxtFext**-learning, requires that all hypotheses output infinitely often must describe the same finite variant of the correct set, while TxtFex** permits the learner to vacillate between finitely many different finite variants of the correct set. In this paper we show that TxtFex** ≠ TxtFext**, thereby answering the question posed by Osherson, et al. We prove this in a strong way by exhibiting a family in TxtFex*2\TxtFext**.
(Journal of Symbolic Logic, 79(3):908-927, 2014)
A. Beros
We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity for the standard notions of finite learning, learning in the limit, behaviourally correct learning and anomalous learning in the limit. In proving the Σ05-completeness result for behaviourally correct learning we prove a result of independent interest; if a u.c.e. family is not learnable, for any computable learner there is a Δ02 enumeration witnessing failure.
Talks
Department Colloquium
(3/27/2015)
University of North Texas
Recursion Theory Seminar
(2/23/2015)
University of California - Berkeley
International Conference on Grammatical Inference 2014
(9/18/2014)
University of Kyoto
Logic Colloquium 2014
(7/15/2014)
Vienna University of Technology
Mathematics Seminar
(6/11/2014)
Université de Nantes
2013 ASL North American Annual Meeting
(5/8/2013 - 5/11/2013)
University of Waterloo
AMS Sectional Meeting
(4/26/2013 - 4/28/2013)
University of Iowa, Ames
Recursion Theory Seminar
(12/5/2012)
University of California - Berkeley
Midwest Computability Seminar XI
(11/15/2012)
University of Chicago
Logic Seminar
(11/14/2012)
University of Wisconsin - Madison
2011 North American Annual Meeting of the ASL
(3/24/2011 - 3/27/2011)
University of California - Berkeley
Teaching
The lecture for Math 252A meets in 414 Keller Hall, MWF 9:30am - 10:20am.

The teaching assistant for this course is Jamal Hassan. His office is 403D Keller Hall. His email address is jamal@math.hawaii.edu.

The course syllabus is available here.

Lecture notes are available here. The notes are not a substitute for the textbook and may contain typos. I am providing them as a companion to the lectures.

During your recitation period, you will work on problems from these worksheets.
8/22/17Problems 1 - 16
8/29/17Problems 17 - 23
9/5/17Problems 24 - 29
9/12/17Problems 30 - 33
9/19/17Problems 34 - 40
9/26/17Problems 41 - 44
10/10/17Problems 45 - 49
10/17/17Problems 50 - 52
10/23/17Problems 52 - 53
10/31/17Problems 54
11/21/17Problems 55 - 57

The formula sheet for the final exam is available here.

Solutions to some assignments are available below.
Worksheet solutions
Quiz #01 solutions
Quiz #02 solutions
Quiz #03 solutions
Quiz #04 solutions
Quiz #05 solutions
Quiz #06 solutions
Quiz #07 solutions
Quiz #08 solutions

Some review materials are listed below.
Spring 2017 Quiz #01 solutions
Spring 2017 Quiz #02 solutions
Spring 2017 Quiz #03 solutions
Spring 2017 Quiz #04 solutions
Spring 2017 Quiz #05 solutions
Spring 2017 Quiz #06 solutions
Spring 2017 Quiz #07 solutions
Spring 2017 Quiz #08 solutions
Spring 2017 Quiz #09 solutions

The homework assignments are listed below. I will modify the assignments slightly over the course of the semester.

HW #1 (due on 8/29/2017)
7.1 1-6, 8, 14, 16, 18, 22, 24, 26, 32, 34, 39
7.2 2,4, 14, 16, 18, 20, 22, 24, 30, 32, 36, 40, 42, 44, 46, 48, 50, 72
HW #2 (due on 9/5/2017)
7.3 1-4, 8, 10, 12, 18, 20, 22, 26, 30, 34, 38, 40, 44, 52, 54, 72, 80, 88, 92, 119, 124
7.4 2, 4, 6, 8, 10, 12, 16, 20, 22, 32, 34, 42, 44, 48, 62, 74, 78, 94
HW #3 (not due)
7.5 6, 10, 12, 14, 16, 21, 22, 23, 29, 30, 34, 38
7.6 8, 12, 16, 22, 30, 32, 34, 38, 40, 48, 52, 54, 58, 63
HW #4 (due on 9/19/2017)
8.1 2, 4, 6, 8, 16, 20, 22, 24, 26, 28, 34, 38, 42
8.2 2, 8, 10, 14, 16, 18, 22, 24, 32, 36, 43, 44
HW #5 (due on 9/26/2017)
8.3 2, 4, 6, 10, 12, 14, 16, 20, 24, 26, 32, 38
8.4 4, 10, 12, 18, 20, 22, 26, 32, 34, 38
8.6 2, 6, 14, 26, 28
HW #6 (due on 10/3/2017)
8.7 4, 6, 12, 18, 22, 24, 26, 28, 32, 34, 38, 40, 50
HW #7 (due on 10/17/2017)
9.1 2, 8, 12, 16, 20, 24, 26, 34, 40, 42, 44, 46, 52, 56, 58, 115
9.2 2, 6, 8, 10, 12, 18, 24, 28, 30, 34, 38, 42, 50
HW #8 (due on 10/24/2017)
9.3 2, 6, 9, 12, 15, 16, 18, 20, 22, 28, 39, 40
9.4 2, 4, 6, 8, 12, 20, 22, 24, 26, 29, 34, 36
9.5 2, 4, 6, 10, 12, 18, 20, 24, 26, 28, 32, 38
HW #9 (due on 11/7/2017)
9.6 2, 4, 6, 8, 12, 14, 18, 22, 24, 32, 34, 36
9.7 2, 4, 8, 10, 12, 16, 22, 24, 26, 32, 41, 48
9.8 2, 4, 8, 10, 12, 18, 20, 24, 26, 28
9.9 2, 4, 6, 14, 16, 18, 19, 20, 22, 36, 42, 43
HW #10 (due on 11/21/2017)
16.1 1, 2, 3, 4, 5, 10,16
16.2 2, 4, 6, 10, 14, 20, 22, 24, 26, 28, 29, 34
HW #11 (due on 12/5/2017)
17.1 1, 5, 7, 9, 24, 28, 30, 35, 37, 40, 60
10.1 1, 3, 13, 15, 16, 22, 23, 28, 34, 49, 54, 58
10.2 1, 3, 8, 13, 15, 18, 19, 21, 27
3.9 1, 3, 5, 9, 12, 13, 15, 17, 21, 23, 25, 27
10.3 1, 3, 5, 7, 9, 15, 17, 19, 23
The lecture for Math 311 meets in 404 Keller Hall, MWF 10:30am-11:20am.

The course syllabus is available here.

Final Exam Study Guide pdf
Final Exam Study Guide Solutions pdf

Project (due on 12/6/2017) pdf

Midterm 2 (due on 11/13/2017) pdf

HW #1 (due on 9/1/2017)
1.1 1, 2, 4, 6, 7
1.2 1,3, 5, 6, 9, 12, 16
HW #2 (due on 9/8/2017)
1.3 4, 5, 8
1.4 6, 9, 13, 15
1.5 2, 5, 10
HW #3 (due on 9/15/2017)
2.1 1, 3, 5, 7, 8
HW #4 (due on 9/22/2017)
2.2 2, 3, 7
2.3 2, 3, 9, 10
HW #5 (due on 9/29/2017)
3.1 8, 15
3.2 4, 9, 12
HW #6 (due on 10/6/2017)
3.3 10, 11, 17
3.4 10, 19
HW #7 (due on 10/20/2017)
3.5 13, 17, 27, 31
3.6 6, 11
3.7 8
4.1 3, 11
HW #8 (due on 10/27/2017)
4.3 9, 10, 14, 20
HW #9 (due on 11/3/2017)
4.4 5, 7, 14, 17
HW #10 (due on 11/27/2017)
4.6 11, 17
5.1 14
5.2 9, 15
HW #11 (due on 12/6/2017)
6.2 3
6.3 5
7.1 5

Useful Programs/Scripts
For a foundations class I taught in Fall 2016, I wrote the following turing machine simulator.

I have implemented several grammatical inference and clustering algorithms in python with tkinter interfaces. I will make them available here soon.

I have designed and implemented a internetworking transfer protocol based on UDP and intended to be used for hole-punching P2P communication.

I have written a python module for executing custom cellular automata.

A colleague needed a demonstration of attracting points for complex-valued functions, so I wrote the following grapher/calculator. In the future, I will implement further functionality.

Personal
I have many interests outside of mathematics and computer science including photography, writing poetry and snorkeling. My brother, Kostas, is also a mathematician and logician.