Algorithms and Complexity Seminar

For Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in Any Order:

This talk consists of two parts.

In the first part, we consider efficient construction of ``composable
core-sets" for basic diversity and coverage maximization problems. A
core-set for a point-set in a metric space is a subset of the point-set

Abstract:  Asynchronous message-passing system is a standard distributed model, where $n$ processors communicate over unreliable channels, controlled by a strong adaptive adversary.

We present a device-independent randomness expansion protocol, involving only a constant number of non signaling quantum devices, that achieves infinite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is exp(−Ω

In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials given by Green and Tao and Kaufman and Lovett give a way of modifying a collection of polynomials F={P1,...,Pm} to a new collection F′, so that the polynomials in F′ are “pseudorandom”.

CHSH_q is the following simple two-player game: two parties are given x,y in F_q uniformly at random, and each must produce an output a,b in F_q$ without communicating to the other. The players objective is to maximize the probability that their outputs satisfy a+b=xy in F_q.

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is O(log2n), where n is the length of the branching program.

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in Rd, our algorithm achieves Oc(dnρ) query time and Oc(n1+ρ+nd) space, where ρ≤7/(8c2)+O(1/c3)+oc(1).

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems.

We discuss algorithms for the private analysis of network data. Such algorithms work on data sets that contain sensitive relationship information (for example, romantic ties).

Property testing, pioneered by Blum, Goldreich, Goldwasser, Luby, Ron, Rubinfeld and Sudan, is the study of extremely fast randomized algorithms for approximate decision making.

We define the following parameter of connected graphs.
For a given graph $G = (V,E)$ we place one agent in each vertex $v \in V$.
Every pair of agents sharing a common edge are said to be acquainted.

Given data stream $D = \{p_1,p_2,...,p_m\}$ of size $m$ of numbers from
$\{1,..., n\}$, the frequency of $i$ is defined as $f_i = |\{j: p_j =
i\}|$. The $k$-th \emph{frequency moment} of $D$ is defined as $F_k =

Fast algorithms for solving linear systems Ax=b when A is symmetric diagonally dominant (SDD) or graph Laplacian have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image pr