Jeff Kinne: Research Assistants

Contents

Current Positions

I am currently taking applications for the summer of 2012. These are the same positions that have been advertised as part of the SURE program. SURE is a program that brings together undergraduate and faculty researchers from many disciplines for once-weekly short presentations and other events (some social). See the SURE website for more information about SURE. Any undergraduate supported by me this summer will be taking part in the SURE program. It is to be determined to what extent a graduate student supported by me would participate in the SURE events.

I have funds to support 2 students full-time for the summer at roughly $3500 for the summer, or I could support some combination of half-time and full-time students - the choice will depend on the preferences of who applies. The exact calendar of dates of work is somewhat flexible, but will include much of the summer of 2012 (10 weeks).

There will be an informational meeting at 12:00pm noon in Root Hall, A-187, on Friday January 27. If you would like to ask questions about what the research will be like, the logistics, etc., please come to this meeting to ask.

Who should apply?

Necessary Background?   The most important indicators of whether a student will be successful in this type of project are: (1) you should be really interested in computer science and mathematics, and (2) you should be able to pick up new concepts relatively quickly on your own (or with a small amount of guidance/hints). You will be doing most of the work on your own, so you need to be able to work independently. A student will be better prepared the more theory and algorithms courses they have taken. But even a student who has only completed introduction to programming might be ready to contribute to the project if they learn quickly and are passionate. I weigh all factors in choosing who to bring onto the project, and discount no-one up front based on which courses they have taken.

Undergraduates and Graduates.   I encourage both undergraduate students and graduate students to apply, if you are interested.

Application

For the summer 2012 research positions, send the following information to me in an email before Friday, February 3, 2012. You can send the information within the email message or as an attachment (word, pdf, etc.).

Make the subject of the email: summer 2012 research application.

  1. Full Name.

  2. Your Major(s), Minor(s).

  3. Are you Undergrad or Graduate, and total number of credits you have completed at ISU (including transfer credits).

  4. List of all CS and Math classes you have taken, what grades you received.

  5. List of all CS and Math classes you are currently taking.

  6. Total GPA, and GPA for just CS and Math classes.

  7. Brief explanation of why you are interested in research. A paragraph should suffice.

  8. Brief explanation of why you are interested in theoretical computer science. A paragraph should suffice.

  9. Recommendations. If you have any professors other than myself that you think can offer advice to me on your qualifications, have them send me an email with a brief explanation of their thoughts. This is not required. Do not have more than two professors send me recommendations.

  10. Other. If there is any other information (e.g., resume/CV, or course project) you think would help me decide if you will be right for the project, feel free to include it. Be concise.

  11. Full time or half time. Are you most interested in working full-time or half-time on this project? Are you willing to work either full-time or half-time? Note that full-time means at least 40 hours/week, and half-time means at least 20 hours/week. To work full-time on this project, you probably should not be doing anything else (taking summer classes, working another job).

After looking over the list of applicants, I will be in touch with those I think might be a good fit for the project. I will talk to each in person to get a better feel for each person to make the final decision of who will work on the project. The SURE program has indicated they will make their final decisions by March 3. I will as well, and will let you know when I have made my final decisions.

Theoretical Computer Science

My personal research is in theoretical computer science, specifically computational complexity. For more on what this means, see my research publications, see Computational Complexity on wikipedia, search the web, or come talk to me. The courses at Indiana State that are closest to my research are the theory and algorithms courses (CS 620, 658, 621, 420/520, 458/558, 303) and some of the math courses. If you greatly enjoyed those courses, you may be interested in research in theoretical computer science.

Unsure?   Suppose you are unsure if you are interested in theoretical computer science, or you have not taken many (or any) of the courses I listed. Do the following excite you? If so, you may be interested in theoretical computer science.

  • The proof that there are infinitely many primes
  • The fact and proof that there are "more" real numbers than rational numbers.
  • The fact and proof that there are "uncomputable" problems that cannot be solved by any computer.
  • The fact that if you could factor numbers fast then RSA cryptography used on the internet would not be secure.
  • The "P versus NP" problem. And in particular, the fact that for many important problems it is completely wide-open how fast they can be solved (maybe really super fast, maybe/probably incredibly ridiculously slow). And the fact that some of the "NP-hard" problems cannot even be approximated unless they can be solved exactly/optimally.
  • Probability and randomized algorithms. For example, the fact that you can determine with high probability whether a string you look at is the same as one your neighbor looks at by only exchanging a very small number of bits with someone else (much fewer bits than the whole string).
  • The fact that relatively simple "divide and conquer" algorithms do better than you might expect for things such as sorting numbers and multiplying matrices. And slightly more complicated algorithms give fast algorithms for problems such as multiplying numbers.
If you are unsure, feel free to come talk to me about what this research is like.

Research Assistants - Type of Work

The basic format is to consider "things we don't know yet" and try to figure them out. This entails learning what is already known and trying to improve on current knowledge. This means most of your time would be spent reading, thinking, and trying things out.

Programming?   Traditional research in theoretical computer science makes use of surprisingly little actual programming: theoretical computer science research is a mix between math proofs and computer science algorithms. However, I am interested in bringing theory of computing and practical programming together more than is often done. So depending on the interests and skills of the individual student, working on research with me could involve large programming projects that have a strong theoretical foundation.

Research Topic?   The exact problem you work on will depend on your interests. It will have to be something I am interested in and can advise you on. But it is critical that you are interested in the topic, so you will determine the direction the research takes (under my guidance, of course). To begin the project, I will take the lead in giving you some background on the types of problems you could work on. Once you are getting comfortable, we will decide together which direction you should go in.

Presentations.   Students will present to me what they have learned and discovered regularly - at least weekly. These presentations will be informal, with me asking questions and potentially helping on some steps (e.g., why is such and such probability < 1?).

By the end of the research project, the goal is that the student has a good background in some aspect of theoretical computer science and has made some nice new observations. The student will write up these observations into a written paper and present the results publicly at Indiana State, and more broadly if appropriate.

Benefits.   Participating in this type of research project is particularly beneficial to those thinking of pursuing further graduate study after leaving ISU. But the project would be beneficial and fun for anyone interested in theory of computing.

Schedule.   There is some flexibility in terms of the schedule. If you have a summer vacation planned, we can probably schedule your 10 work-weeks around that.

Current Project Description

For the summer 2012 research project, I have the following project in mind. This is the description that has been advertised as part of the SURE program, and this will be the starting point for the summer project. The particular path the project takes will depend on the interests of the students working on the project, and which avenues of investigation prove most fruitful.

Project Title.   Randomized Algorithms and Pseudorandom Generators

Project Description.   Project Description: This project lies within computer science and mathematics, and could potentially benefit from interaction with the computational sciences. The faculty mentor is an expert in theoretical computer science. The project will study randomized algorithms and pseudorandom bit generators, with the goal of marrying theoretical constructions and those used in practice.

A student need not be familiar with these terms to work on the project: the faculty mentor will help provide the necessary background. The main requirement is a strong interest in computer science and mathematics and the drive to seek answers to intriguing questions.

Elegant randomized algorithms are known for a range of problems, i.e., sorting numbers, approximating optimization problems, and simulating physical systems. In some settings, theoretical computer scientists have shown that strong pseudorandom generators could be used to get the same benefits without a need for randomness, though these results have not been developed for use in practice. On the other hand, many practical uses of randomness do not have as strong of a theoretical foundation.

The goal of the project is to see if ideas and techniques from theoretical computer science can give a stronger theoretical foundation to practical uses of randomness, and to see if constructions from theoretical computer science can be made more practical.