# Past Events

# Streaming Algorithms using Finger Printing Technique

## Speaker:

## Time:

## Venue:

Algorithms working on large data(say of size n) should be both space and time efficient. Any algorithm has to see atleast the whole data once, so time required has to be atleast n(see sublinear time algorithms for exceptions).

# Communication in Subclasses of Petri Nets

## Speaker:

## Time:

## Venue:

Petri net theory has nice theorems which relate subclasses of Petri nets defined by structural conditions -- for example T-nets (also known as marked graphs) and free choice nets -- to their behavioural properties -- such as checking, given a net

# How to Generate a Large String almost Uniformly at Random, with a Small Number of Coin Tosses?

## Speaker:

## Time:

## Venue:

Computer scientists devise randomized algorithms when they cannot find good deterministic ones. Then they try to decrease the randomness used and still try to prove that the algorithm answers correctly with high probability.

# A Non-cooperative Perspective of Multi-user Communications

## Speaker:

## Time:

## Venue:

The scarcity of spectrum is becoming an impediment to the growth of more capable wireless networks.

# Reducibility Among Fractional Stability Problems

## Speaker:

## Time:

## Venue:

In a landmark paper, Papadimitriou introduced several syntactic subclasses of the search class TFNP (Total Function Nondeterministic Polynomial) based on proof styles that (unlike TFNP) admit complete problems.

# A Glimpse of Future Technologies Research at Intel

## Speaker:

## Time:

## Venue:

We will present a broad range of longer-term research at Intel Labs, ranging from sensing/perception to networking to exascale computing.

# Perturbed Identity Matrices have High Rank: Proof and some Applications

## Speaker:

## Time:

## Venue:

We will discuss a lower bound (due to Noga Alon) on the rank of any real matrix in which all the diagonal entries are significantly larger (in absolute value) than all the other entries.

# Sparse Solutions to Under-determined Systems of Linear Equations

## Speaker:

## Time:

## Venue:

An under-determined system of linear equation has infinitely many solutions (if it has a solution).

# Probably Approximately CORRECT Learning

## Speaker:

## Time:

## Venue:

We will see the definition of Probably Approximately CORRECT Learning. Then we will prove that its easy to learn about Rectangles and Conjunctions but hard to learn about 3-Term Disjunctions.