Colloquium Series
Fall 2014
All talks are from 3:454:45 p.m. in the Colloquium Room, unless otherwise specified.

Dec03

Edgeweighted Cayley graphs and pary bent functionsTime: 03:45 PM
View Abstract
Bent functions are important in encryption algorithms. We will discuss bent pary functions f:GF(p)^n \to GF(p), where p is a prime, f is even, and f(0)=0. Associated to a pary function is an edgeweighted Cayley graph whose vertices correspond to points in GF(p)^n and whose edges are weighted by elements of GF(p). There is an edge of weight j from vertex u to vertex v if f(uv)=j. We define edgeweighted strongly regular graphs and show how they are related to symmetric weighted partial difference sets and association schemes. We construct a family of pary bent functions whose "level curves" give a strongly regular decomposition of the complete graph on n^2 vertices, and such that each subgraph of the decomposition is of Latin square type. The talk is based on joint work with David Joyner, David Phillips, Charles Celerier, and Steven Walsh.

Nov19

Construction of Nonstandard Finite Difference SchemesProf. Talitha WashingtonHoward UniversityTime: 03:45 PM

Nov12

Multiple zeta values of even arguments (and some analogous results)Prof. Mike HoffmanUSNATime: 03:45 PM
View Abstract
The sum of all convergent multiple zeta values of a given length and weight n is just \zeta(n). This result was proved first by Euler for length 2, by Courtney Moen for length 3, and by Don Zagier and Andrew Granville for arbitrary length. Given n, what can we say about the the sum of all multiple zeta values with fixed length, even arguments, and weight 2n? Again for length 2 the result goes back to Euler. But for the arbitrarylength case was not considered until 2012, when I gave a general result. I will explain the result, and also describe some analogous results proved by other authors.

Oct24

Hallucination Helps: Energy Efficient Virtual Circuit RoutingProf. Clifford SteinColumbia UniversityTime: 12:00 PM
View Abstract
In this talk, we give online and offline approximation algorithms for energy efficient circuit routing protocols for a network of components that are speed scalable, and that may be shutdown when idle. We will consider both the case where the speedscalable components are edges and the case when they are nodes. For the case of edges, we describe a polynomialtime offline algorithm that has a polylog approximation ratio. The key step of the algorithm design is a random sampling technique that we call hallucination. The algorithm extends rather naturally to an online algorithm. The analysis of the online algorithm introduces a natural ``priority'' multicommodity flow problem, and bounds the priority multicommodity flowcut gap. We will then explain the additional difficulty faced if the power management components are vertices, and explain how to how to surmount this difficulty in the offline case. This work spans several papers and is joint with Antonios Antoniadis, Nikhil Bansal, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs.

Sep24

The USNA Powered Flight Program and a binary integer programming solution to its daily flight scheduling problemLT Peter BarkleyUSNATime: 03:45 PM

Sep18

Change of phase for the humid atmosphere: a model of nonlinear discontinuous equationProf. Roger TemamIndiana UniversityTime: 12:00 PM
View Abstract
In this lecture we will recall the atmospheric equations of water vapor with saturation. In their simplest form, these equations form a nonlinear system of partial differential equations with discontinuities corresponding to the change of phase. We will address the issues of the definition of the solutions, in the context of convex analysis and variational inequalities, and establish some results on the existence, uniqueness and regularity of these solutions.

Sep16

Opt ArtProf. Robert BoschOberlin CollegeTime: 03:45 PM
View Abstract
Optimization is concerned with optimal performancefinding the best way to complete a task. It has been put to good use in a great number of diverse disciplines: advertising, agriculture, biology, business, economics, engineering, manufacturing, medicine, telecommunications, and transportation (to name but a few). In this lecture, we will showcase its amazing utility by demonstrating its applicability in the area of visual art, which at first glance would seem to have no use for it whatsoever! We will begin by describing how to use integer programming to construct a portrait out of complete sets of double nine dominoes. We will then describe how high quality solutions to certain largescale traveling salesman problems can lead to beautiful continuous line drawings. We will conclude by presenting other examples of Opt Artart constructed with the assistance of optimization techniques.

Sep10

Optimal Patrol to Detect Attacks at Dispersed Heterogeneous LocationsCDR Dick McGrathUSNATime: 03:45 PM
View Abstract
We study a patrol problem where several patrollers move between heterogeneous locations dispersed throughout an area of interest in order to detect enemy attacks. To formulate an effective patrol policy, the patrollers must take into account travel time between locations, as well as locationspecific parameters, which include patroller inspection times, enemy attack times, and cost incurred due to an undetected attack. We consider both random and strategic attackers. A random attacker chooses a location to attack according to a probability distribution, while a strategic attacker plays a twoperson zerosum game with the patrollers. In some cases, we can compute the optimal solution using linear programming. This method, however, becomes computationally intractable as the problem size grows. Therefore, we focus on developing efficient heuristics, based on aggregate index values, fictitious play, and shortest paths. Numerical experiments demonstrate that our heuristics produce excellent results with computation time orders of magnitude less than what is required to compute the optimal solution.

Sep03

Optimal Future Sensor Allocation ProblemProf. Christopher GriffinPenn State UniversityTime: 03:45 PM
View Abstract
In this talk we consider the problem of sensing a finite set of (moving) objects over a finite planning horizon using a set of sensors in prefixed locations that vary with respect to time over a discretized space. We formulate an integer programming problem that maximizes a quality of sensor return given either deterministic or probabilistic (i.e., forecasted) object routes. We examine the computational complexity of the problem and show it is NPHard. We analyze a representative data set of potential sensor collects and show, surprisingly, a near linear growth in computation time. We explain this discrepancy by identifying a class of subproblems (to which our data set belongs) that can be solved by a greedy heuristic. We then construct an artificial data set and illustrate nonlinear solution time growth. Finally, we define an alternate strongly polynomial (greedy) heuristic for solving the problem and investigate quality bounds.

Aug21

Finite Time and Aperiodically Time Dependent Dynamics: The Research LandscapePast, Present, and FutureProf. Stephen WigginsUniversity of Bristol (UK)Time: 12:00 PM