# Department of Computer Science

### Contact Information

Department Chair
Desmond Lun

Department Secretary
Sharon Moore

Jean-Camille Birget

Suneeta Ramaswami

### Student Spotlight

We R Arts and Sciences: Branden Bortner

If anyone has their doubts about the positive effects of playing video games or spending time in front of a computer, they need not look any further than Branden Bortner’s success. Branden arrived at Rutgers–Camden having already taken college level courses as a high school student. He even took an AP course in computer science ... Read more ... Read more ...

Home » Research Areas » Computer Science/Math Seminars

## Computer Science/Math Seminars

Please send an email to Sharon Moore, the department secretary, at shamoore@camden.rutgers.edu to be included on the seminar mailing list.

### Scott Kiskaddon and Joseph Rhodes

Students under the supervision of Dr. Joseph Gerver

#### Thursday, April 2412:30-1:20p.mBSB 134

Abstract: A classic algorithm in economics solves the following problem: Suppose there are n players, each owning one of n different items, and suppose that each player assigns a personal value to each item, with a strict ranking among the values.  How should the players trade their items with each other, in order to maximize the total personal value of the items they end up with?

In real life, the assumption of a strict ranking seems artificial. We encounter indifferences everywhere, from what we choose to eat, to what type of car we drive. Therefore, when handling the problem of how to order trades between people, it is reasonable to take indifferences into account. As a result, we face the question of how to break a tie; that is, when players may be assigned to one of two (or more) items they are indifferent between.

Our theoretical model solves this problem without inducing strict preferences. Due to the overwhelming complexity of problems with a large number of players, our algorithm approximates the solution with highest aggregate value, with 95% confidence of a probability between .95 and 1, in polynomial time.

### Dr. Mahesh Nerukar

#### Topological Dynamics of $(X,T)$ via Families of Subsets of $T$

##### Thursday, April 1712:30-1:20p.m.BSB 134

Abstract: A topological dynamical system $(X,T)$ consist of a compact metric space along with a (jointly continuous) : action $(x,t)\to xt$, of a topological group $T$. A minimal system is the one with no proper closed invariant subsets and classifying all minimal systems is an impossible task, even when $T$ is the group of integers. In the early sixties, Professor Hillel Furstenberg proved a deep structure theorem describing how such systems are built’ as a tower’ starting with the most trivial system consisting one just one point space at the base. The tower’ consists of a sequence of extensions with specific dynamical properties’. The systems in this tower for $(X,T)$ can be thought in terms of $T$ invariant closed equivalence relations on $X$. The first non-trivial factor in this tower–the so called–maximal equicontinuous factor’ of $(X,T)$ is intimately connected with the notion of regional proximality’. Two points $x$ and $y$ in $X$ are regionally proximal if we can find sequences $x_n,y_n\in X$, $t_n\in T$ and $z\in X$, such that $x_n\to x$, $y_n\to y$ and $(x_nt_n\,,y_nt_n)\to (z,z)$. One of the first deep result in Topological Dynamics says that under suitable conditions on $(X,T)$, the relation of being regionally proximal is an equivalence relation on $X$. In 1968 , using a Harmonic analysis result’ of Folner, W. Veech gave a mysterious proof’ of this result when $T$ is abelian. (There are other conditions implying the same conclusion, e.g. existence of a $T$ invariant Borel probability measure on $X$).

In my talk I shall give a completely different approach to these questions (in particular to the Veech theorem), using ideas motivated by the fascinating theory of the `structure of recurrence’ which evolved in the past three decades in efforts to prove results of combinatorial Number Theory using Topological Dynamics. I shall make all the precise statements understandable to our graduate/upperlevel-undergraduate students.

### Tim Hearn

Student, Rutgers University–Camden

#### Cuckoo Hashing

##### Thursday, March 2712:30-1:20p.m.BSB 134

Abstract: A new and interesting way of hashing designed to guarantee constant time look-up and deletion – even in the worst case.  No prior knowledge of hashing is needed.  The talk will focus on some challenges related to this type of hashing scheme,  what has been done to overcome them, and what still remains a challenge today.

### Professor Howard Jacobowitz

#### Haefliger Foliations and an Application to CR Structures

##### Thursday, February 612:30-1:20p.m.BSB 134

Abstract: A k-dimensional foliation of a manifold is a decomposition of the manifold by manifolds of dimension k. Think of the coordinate plane being filled out by horizontal lines or the torus by circles. The interesting questions are global ones. In particular, when does the manifold admit such a foliation? About fifty years ago, Haefliger and others reduced many of these questions to problems in classical algebraic topology. This approach also was used (by Gromov and Landweber) to prove that a wide class of open manifolds admit complex structures. Similar techniques seem to suffice to establish the existence of partial complex structures (CR structures).

Professor Takeo Ohsawa

Graduate School of Mathematics
Nagoya University, Japan

#### Questions and visions of several complex variables

##### Tuesday, December 3, 201312:25pm – 1:20pmBusiness & Science Building – Room 117

AbstractKiyoshi Oka had, as a pioneer of several complex variables, a very original viewpoint. In 1947, he wrote about it in a letter to Teiji Takagi who is known by his work in class field theory. Questions that motivated the development of several complex variables will be discussed in connection to such visions of mathematics.

The Department of Computer Science and the Department of Mathematical Sciences Present:

### Dr. Guy Kortsarz

Department of Computer Science
Rutgers University – Camden

#### Introduction to fixed parameter tractable algorithms

##### Thursday, November 21, 201312:25pm – 1:20pmBusiness & Science Building – Room 117

AbstractThe talk is an introductory talk to the subject of fixed parameter tractability. No prior knowledge is required albeit it would be nice if the theory of NP Completeness would be known. Given that many problems are NP-Hard we do not expect to solve this (at least not on the hard instances) in polynomial time. Fixed parameter tractability is one of the various ways to cope with this unfortunate situation. Identify a parameter k related to the problem (the optimum size, the tree width, etc.) and allow time f(k) poly(n) with f possibly exponential or worse.

Give an exact solution in this time. For example the Vertex Cover problem is, given a graph G(V,E), to find a minimum-size V’ so that for every edge e = (u,v), either u is in V’ or v is in V’. It is NP-hard. We shall show a 2^k poly(n) exact solution for Vertex Cover. The same holds for the problem of finding a path of length k, finding k disjoint triangles, and a huge many more problems. I will survey some basic techniques.

The Department of Computer Science and the Department of Mathematical Sciences Present:

### Dr. Gabor Toth

Department of Mathematical Sciences
Rutgers University – Camden

#### Stability of Geometric Inequalities for Convex Sets

##### Thursday, November 14, 201312:25pm – 1:20pmBusiness & Science Building Room 132

Abstract: In a geometric inequality, equality usually holds for a well-defined extremal class of geometric objects. The stability problem is the following: If for some geometric object the inequality is close to being equality, how close is then the object to being extremal? We will give several examples of stability for Minkowski type measures of symmetries of convex sets in terms of the Hausdorff and Banach-Mazur distance.

The Department of Computer Science and the Department of Mathematical Sciences present:

### Dr. Mauro Garavello

Department of Mathematics and Applications
University of Milan

#### Balance Laws and ODEs

##### Thursday, September 26, 201312:25pm – 1:15pmBusiness & Science Building Room 336

Abstract: In the talk we consider a system of hyperbolic balance laws coupled, through the boundary data, with ordinary differential equations.  For such a system, we discuss existence, continuous dependence and stability of solutions.  A set of possible applications motivate the study of this kind of problems.