Physical Sciences and Mathematics Commons^™

Optimal Cryptographic Hardness Of Learning Monotone Functions, Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee

Publications and Research

Over the years a range of positive algorithmic results have been obtained for learning various classes of monotone Boolean functions from uniformly distributed random examples. Prior to our work, however, the only negative result for learning monotone functions in this model has been an information-theoretic lower bound showing that certain super-polynomial-size monotone circuits cannot be learned to accuracy 1/2+w(log n/ p n) (Blum, Burch, and Langford, FOCS’98). This is in contrast with the situation for nonmonotone functions, where a wide range of cryptographic hardness results establish that various “simple” classes of polynomial-size circuits are not learnable by polynomial-time algorithms.

In …

Correlating Molecular Phylogeny With Venom Apparatus Occurrence In Panamic Auger Snails (Terebridae), Mandë Holford, Nicolas Puillandre, Maria Vittoria Modica, Maren Watkins, Rachel Collin, Eldredge Bermingham, Baldomero M. Olivera

Publications and Research

Central to the discovery of neuroactive compounds produced by predatory marine snails of the superfamily Conoidea (cone snails, terebrids, and turrids) is identifying those species with a venom apparatus. Previous analyses of western Pacific terebrid specimens has shown that some Terebridae groups have secondarily lost their venom apparatus. In order to efficiently characterize terebrid toxins, it is essential to devise a key for identifying which species have a venom apparatus. The findings presented here integrate molecular phylogeny and the evolution of character traits to infer the presence or absence of the venom apparatus in the Terebridae. Using a combined dataset …

Pointcut Rejuvenation: Recovering Pointcut Expressions In Evolving Aspect-Oriented Software, Raffi T. Khatchadourian, Phil Greenwood, Awais Rashid, Guoqing Harry Xu

Publications and Research

Pointcut fragility is a well-documented problem in Aspect-Oriented Programming; changes to the base-code can lead to join points incorrectly falling in or out of the scope of pointcuts. We present an automated approach that limits fragility problems by providing mechanical assistance in pointcut maintenance. The approach is based on harnessing arbitrarily deep structural commonalities between program elements corresponding to join points selected by a pointcut. The extracted patterns are then applied to later versions to offer suggestions of new join points that may require inclusion. We demonstrate the usefulness of our technique by rejuvenating pointcuts in multiple versions of several …

Contributing Factors To Pointcut Fragility, Phil Greenwood, Awais Rashid, Raffi T. Khatchadourian

Publications and Research

Pointcut fragility is a well-documented problem of Aspect-Oriented Programming with changes to the base-code causing join points to incorrectly fall in or out of scope. In order to combat this problem a tool was developed that provides mechanical assistance to pointcut maintenance. This tool relied on the deep structural commonalities between program elements to detect when pointcut fragility occurs. During the assessment of this tool a number of common practices were uncovered that were employed both in the aspect and base-code that contributed to or prevented pointcut fragility. This paper documents the practices uncovered and describes how they can affect …

Quantum Computing: Selected Internet Resources For Librarians, Researchers, And The Casually Curious, Jill Cirasella

Publications and Research

This article is an annotated selection of the most important and informative Internet resources for learning about quantum computing, finding quantum computing literature, and tracking quantum computing news.

The Maximum Rectilinear Crossing Number Of The N Dimensional Cube Graph, Matthew Alpert, Elie Feder, Heiko Harborth, Sheldon Klein

Publications and Research

We find a.nd prove the maximum rectilinear crossing n1.1mber of the three-dimensional cube graph (Q₃). We demonstrate a method of drawing then-cube graph, Q_n., with many crossings, and thus find a lower bound for the maximum rectilinear crossing number of Q_n. We conjecture that this bound is sharp. We also prove an upper bound for the maximum rectilinear crossing number of Q_n.

Tr-2009002: Cartesian Closed Categories For The Logic Of Proofs, Florian Lengyel

Computer Science Technical Reports

No abstract provided.

Tr-2009004: An Investigation Report On Auction Mechanism Design, Jinzhong Niu, Simon Parsons

Computer Science Technical Reports

No abstract provided.

Tr-2009005: Visual Analytics: A Multi-Faceted Overview, Ilknur Icke, Elizabeth Sklar

Computer Science Technical Reports

No abstract provided.

Tr-2009007: History Tree Descriptors Of Grayscale Images, Gabor T. Herman, T. Yung Kong, Lucas M. Oliveira

Computer Science Technical Reports

No abstract provided.

Tr-2009006: Intelligent Players, Sergei Artemov

Computer Science Technical Reports

No abstract provided.

Tr-2009013: Generalized Gillespie Stochastic Simulation Algorithm And Chemical Master Equation Using Timing Machinery, Ellis D. Cooper, Florian Lengyel

Computer Science Technical Reports

No abstract provided.

Tr-2009012: Rational Decisions In Non-Probabilistic Settings, Sergei Artemov

Computer Science Technical Reports

No abstract provided.

Tr-2009014: Randomized Preprocessing Of Homogeneous Linear Systems, Victor Y. Pan, Guoliang Qian

Computer Science Technical Reports

No abstract provided.

Tr-2009016: On The Effectiveness Of Projection Methods For Convex Feasibility Problems With Linear Inequality Constraints, Yair Censor, Wei Chen, Patrick L. Combettes, Ran Davidi, Gabor T. Herman

Computer Science Technical Reports

No abstract provided.

Tr-2009001: Bisc: A Binary Itemset Support Counting Approach Towards Efficient Frequent Itemset Mining, Jinlin Chen, Keli Xiao

Computer Science Technical Reports

No abstract provided.

Tr-2009003: On Proof Realization On Modal Logic, Ren-June Wang

Computer Science Technical Reports

No abstract provided.

Tr-2009008: Randomized Preprocessing Of Homogeneous Linear Systems Of Equations, Victor Y. Pan, Guoliang Qian

Computer Science Technical Reports

No abstract provided.

Tr-2009009: Solving Linear Systems With Randomized Augmentation, Victor Y. Pan, Guoliang Qian

Computer Science Technical Reports

No abstract provided.

Tr-2009010: Randomized Preconditioning Versus Pivoting, Victor Y. Pan, Guoliang Qian, Ai-Long Zheng

Computer Science Technical Reports

No abstract provided.

Tr-2009011: Knowledge-Based Rational Decisions, Sergei Artemov

Computer Science Technical Reports

No abstract provided.

Tr-2009015: Knowledge-Based Rational Decisions And Nash Paths, Sergei Artemov

Computer Science Technical Reports

No abstract provided.

Lattice Operators And Topologies, Eva Cogan

Publications and Research

Working within a complete (not necessarily atomic) Boolean algebra, we use a sublattice to define a topology on that algebra. Our operators generalize complement on a lattice which in turn abstracts the set theoretic operator. Less restricted than those of Banaschewski and Samuel, the operators exhibit some surprising behaviors. We consider properties of such lattices and their interrelations. Many of these properties are abstractions and generalizations of topological spaces. The approach is similar to that of Bachman and Cohen. It is in the spirit of Alexandroff, Frolík, and Nöbeling, although the setting is more general. Proceeding in this manner, we …

The Most Effective Statistical Approach To Correct Environmental Satellite Data, Md Zahidur Rahman, Leonid Roytman

Publications and Research

The proposed paper apply novel statistical approach to correct radiometric data measured by Advanced Very High Resolution Radiometers (AVHRR) onboard the National Oceanic and Atmospheric Administration (NOAA) Polar Orbiting Environmental Satellites (POES). This paper investigates Normalized Difference Vegetation Index (NDVI) stability in the NOAA/NESDIS Global Vegetation Index (GVI) data during 1982-2003. AVHRR weekly data for the five NOAA afternoon satellites for the China dataset is studied, for it includes a wide variety of different ecosystems represented globally. It was found that data for the years 1988, 1992, 1993, 1994, 1995 and 2000 are not stable enough compared to other years …

Biodegradation Of Fuel Oxygenates In Northeastern United States Aquifers With An Analysis Of Underground Storage Tank Leaks, Gordon Hinshalwood

Dissertations, Theses, and Capstone Projects

During the past decade the application of monitored natural attenuation has become one of the predominant technologies used in the remediation of gasoline spills impacting subsurface soils and groundwater. The success of this method has depended, for the most part, on the biodegradation of those gasoline constituents that dissolve into groundwater and transport with the groundwater most readily.

One of the most mobile components of gasoline formulations during the past 20 years has been methyl tertiary butyl ether (MTBE), which has traditionally been viewed in both the scientific and the regulatory communities as relatively recalcitrant to biodegradation. However, cases of …

Flocking In The Time-Dissonance Plane, Adam James Wilson

Publications and Research

This paper describes a technique for the sonification of an idealized model of the flocking behavior of birds, fish, and insects. Flocking agents are represented by pitches that move through time to produce chords of variable dissonance. The objective of each agent is to move toward more consonant chord formations with other agents. The output of the sonification is intended to provide material for use in musical composition.

Series That Probably Converge To One, Thomas J. Pfaff, Max Tran

Publications and Research

No abstract provided.

The Maximum Of The Maximum Rectilinear Crossing Numbers Of D-Regular Graphs Of Order N, Matthew Alpert, Elie Feder, Heiko Harborth

Publications and Research

We extend known results regarding the maximum rectilinear crossing number of the cycle graph (Cn) and the complete graph (Kn ) to the class of general d-regular graphs Rn,d. We present the generalized star drawings of the d-regular graphs Sn,d of order n where n + d ≡ 1 (mod 2) and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of Sn,d for n ≡ d ≡ 0 (mod 2) is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by …

The Orchard Crossing Number Of An Abstract Graph, Elie Feder, David Garber

Publications and Research

.We introduce the Orchard crossing number, which is defined in a similar way to the well-known rectilinear crossing number. We compute the Orchard crossing number for some simple families of graphs. We also prove some properties of this crossing number.

Moreover, we define a variant of this crossing number which is tightly connected to the rectilinear crossing number, and compute it for some simple families of graphs.

On The Dynamics Of Quasi-Self-Matings Of Generalized Starlike Complex Quadratics And The Structure Of The Mated Julia Sets, Ross Flek

Dissertations, Theses, and Capstone Projects

It has been shown that, in many cases, Julia sets of complex polynomials can be "glued" together to obtain a new Julia set homeomorphic to a Julia set of a rational map; the dynamics of the two polynomials are reflected in the dynamics of the mated rational map. Here, I investigate the Julia sets of self-matings of generalized starlike quadratic polynomials, which enjoy relatively simple combinatorics. The points in the Julia sets of the mated rational maps are completely classified according to their topology. The presence and location of buried points in these Julia sets are addressed. The interconnections between …