Engineering Commons^™

Password Protected Visual Cryptography Via Cellular Automaton Rule 30, Roman V. Yampolskiy, Jovan D. Rebolledo-Mendez, Musa M. Hindi

Faculty Scholarship

Visual cryptography depends on two shares. The initial configuration, extra security bits and the number of the rule for the CA along with the number of computed steps serve as a password for a visually encrypted image. The second share could contain a predefined pattern; the developed algorithm uses a snapshot of a CA after a certain number of steps to generate the predefined share. Only one of these shares has to be random. The developed encryption system is a hybrid between visual and classical cryptographic approaches. It requires less storage space compared to a standalone visual encryption system and …

Efficiency Theory: A Unifying Theory For Information, Computation And Intelligence, Roman V. Yampolskiy

Faculty Scholarship

The paper serves as the first contribution towards the development of the theory of efficiency: a unifying framework for the currently disjoint theories of information, complexity, communication and computation. Realizing the defining nature of the brute force approach in the fundamental concepts in all of the above mentioned fields, the paper suggests using efficiency or improvement over the brute force algorithm as a common unifying factor necessary for the creation of a unified theory of information manipulation. By defining such diverse terms as randomness, knowledge, intelligence and computability in terms of a common denominator we are able to bring together …

Turing Test As A Defining Feature Of Ai-Completeness, Roman V. Yampolskiy

Faculty Scholarship

The paper contributes to the development of the theory of AI-Completeness by formalizing the notion of AI-Complete, C-Complete and AI-Hard problems. The intended goal is to provide a classification of problems in the field of Artificial General Intelligence. We prove Turing Test to be an instance of an AI-Complete problem and further show certain AI problems to be AI-Complete or AI-Hard via polynomial time reductions. Finally, the paper suggests some directions for future work on the theory of AI-Completeness.

Learning Visual Features For The Avatar Captcha Recognition Challenge, Mohammed Korayem, Abdallah A. Mohamed, David Crandall, Roman Yampolskiy

Faculty Scholarship

Captchas are frequently used on the modern world wide web to differentiate human users from automated bots by giving tests that are easy for humans to answer but difficult or impossible for algorithms. As artificial intelligence algorithms have improved, new types of Captchas have had to be developed. Recent work has proposed a new system called Avatar Captcha, in which a user is asked to distinguish between facial images of real humans and those of avatars generated by computer graphics. This novel system has been proposed on the assumption that this Captcha is very difficult for computers to break. In …

Development Of Embedded Captcha Elements For Bot Prevention In Fischer Random Chess, Ryan Mcdaniel, Roman V. Yampolskiy

Faculty Scholarship

Cheating in chess can take many forms and has existed almost as long as the game itself. The advent of computers has introduced a new form of cheating into the game. Thanks to the computational power of modern-day computers, a player can use a program to calculate thousands of moves for him or her, and determine the best possible scenario for each move and countermove. These programs are often referred to as "bots," and can even play the game without any user interaction. In this paper, we describe a methodology aimed at preventing bots from participating in online chess games. …

Construction Of An Np Problem With An Exponential Lower Bound, Roman V. Yampolskiy

Faculty Scholarship

In this paper we present a Hashed-Path Traveling Salesperson Problem (HPTSP), a new type of problem which has the interesting property of having no polynomial time solutions. Next we show that HPTSP is in the class NP by demonstrating that local information about sub-routes is insufficient to compute the complete value of each route. As a consequence, via Ladner"s theorem, we show that the class NPI is non-empty.

Some Skepticism About Search Neutrality, James Grimmelmann

Faculty Scholarship

In the last few years, some search-engine critics have suggested that dominant search engines (i.e. Google) should be subject to “search neutrality” regulations. By analogy to network neutrality, search neutrality would require even-handed treatment in search results: It would prevent search engines from playing favorites among websites. Academics, Google competitors, and public-interest groups have all embraced search neutrality.

Despite this sudden interest, the case for search neutrality is too muddled to be convincing. While “neutrality” is an appealing-sounding principle, it lacks a clear definition. This essay explores no fewer than eight different meanings that search-neutrality advocates have given the term. …

Assessing The Legal Risks In Network Forensic Probing, Michael Losavio, Olfa Nasraoui, Vincent Thacker, Jeff Marean, Nick Miles, Roman Yampolskiy, Ibrahim Imam

Faculty Scholarship

This paper presents a framework for identifying the legal risks associated with performing network forensics on public networks. The framework is discussed in the context of the Gnutella P2P network protocol for which the legal issues related to authorized access have not yet been addressed.

Embedded Noninteractive Continuous Bot Detection, Roman V. Yampolskiy, Venu Govindaraju

Faculty Scholarship

Multiplayer online computer games are quickly growing in popularity, with millions of players logging in every day. While most play in accordance with the rules set up by the game designers, some choose to utilize artificially intelligent assistant programs, a.k.a. bots, to gain an unfair advantage over other players. In this article we demonstrate how an embedded noninteractive test can be used to prevent automatic artificially intelligent players from illegally participating in online game-play. Our solution has numerous advantages over traditional tests, such as its nonobtrusive nature, continuous verification, and simple noninteractive and outsourcing-proof design. © 2008 ACM.