Theory  Seminar

 

 

Wednesday 12:30 -- 13:30

Seminari Room (III floor)

Dipartimento di Informatica

Via Salaria 113 

 

 

Fall 2009-2010

 

(9 Dec) Tiziana Calamoneri - (Sapienza University) 

Title: Voronoi Diagrams, Laguerre Measure and Deployments of mobile Sensors

Abstract

We address the problem of deploying heterogeneous mobile sensors over a target area. We show how

traditional approaches designed for homogeneous networks fail when adopted in the heterogeneous

operative setting. Unfortunately, network and device homogeneity is an unrealistic assumption

in most practical deployments. In order to deal with realistic scenarios, we introduce  a generalization of the Voronoi

approach based on Laguerre geometry. We will particularly highlight the theoretical aspects of

this work and prove the appropriateness of our approach to the management of heterogeneous networks.

 

(2 Dec) Olaf Beyersdorff   (Hannover University) 

Title: Proof Systems that takes Advice

One of the starting points of propositional proof complexity is the  seminal paper by Cook and Reckhow (JSL 79), where they defined

propositional proof systems as poly-time computable functions which have  all propositional tautologies as their range.

Motivated by provability  consequences in bounded arithmetic, Cook and Krajicek (JSL07) have  recently started the

investigation of proof systems which are computed by  poly-time functions using advice. While this yields a more powerful model,

it is also less directly applicable in practice.

 

In this talk we describe recent results on this new model of proof systems.

In particular, we investigate the following questions:

 

1) Do there exist optimal or p-optimal proof systems with advice?

2) Do there exist polynomially bounded proof systems with advice?

3) Does the usage of advice shorten propositional proofs?

 

While the first question receives an affirmative answer, we obtain  different characterizations for the second one, depending on the

complexity of the underlying language and the amount and type of the  advice used by the proof system. To approach the third question,

we  compare proof systems with advice with both classical advice-free systems  and proof systems using an easy oracle.

 

 

 

Spring 2008-2009

 

(1 Jul) Emanuele Viola - (Northeastern University) 

Title: Lower bounds for succinct data structures


Abstract:  

It's the end of the semester, and you need to store on a computer
 your N students' grades from the 3-element universe {pass, fail, borderline}. 
Via so-called arithmetic coding you can store them using the minimum number of bits, 
N(log_2 3) + O(1), but then to retrieve a grade you need to read all the bits.
 Or you can use two distinct bits per grade, but then you waste a linear 
amount of space.
A breakthrough by Patrascu (FOCS 2008), later refined with Thorup, shows how to store 
the grades using the minimum number of bits so that each grade can be retrieved by 
reading just O(log N) bits.  We prove a matching lower bound: To retrieve the 
grades by reading b bits, space N(log_2 3) + N/2^b is necessary.  We also prove 
lower bounds for other fundamental data structure problems, including: storing a 
set so that membership queries can be answered efficiently, storing a bit-string so 
that prefix sums can be computed efficiently, and storing a string of brackets so 
that matching brackets can be found efficiently.

 

 

(6 May) Blerina Sinaimeri - (La Sapienza DI)

Title: Multigraphs (only) satisfy a weak triangle removal lemma

Abstract: (Asaf Shapira and Raphael Yuster, Electron. J. Combin., 16
(2009), http://www.math.tau.ac.il/~asafico/multiremoval.pdf )

The triangle removal lemma states that a simple graph with o(n3)
triangles can be made triangle-free by removing o(n2) edges. It is
natural to ask if this widely used result can be extended to
multi-graphs. Here we rule out the possibility of such an extension by
showing that there are multi-graphs with only n^(2+o(1)) triangles
that are still far from being triangle-free. On the other hand, we
show that for some slowly growing function g(n) = \omega(1), if a
multi-graph has only g(n)n2 triangles then it must be close to being
triangle-free. The proof relies on variants of the Ruzsa-Szemer_di
theorem.

 

(29  Apr) Nicola Galesi - (La Sapienza DI)

Title: An open problem on minimally unsatisfiable kDNFs

Abstract:  

A kDNF is a boolean expression obtained as a conjuntion of a disjunction of k-terms (i.e. conjuntions with at most k literals).  
A CNF is simply a 1-DNF. A folklore result says that minimally unsatifiable CNFs (MU-CNF), i.e. unsat CNFs which switch to 
satisfiable by removing any clause, have strictly more clauses than variables. What is the minimal size of a MU-kDNF
 that mentions n variables ? In the talk I’ll present a recent result of Eli Ben-Sasson and Jakob Nordstrom, [B-SN09], proving that a MU-kDNF 
over n variables must have size at least (n/k)^(1/(k+1)). This is the main technical result in [B-SN09], whose main 
topic is proof complexity. The [B-SN09] bound on MUk-DNFs is the only known result. Proving its tighteness or improve it 
is an interesting combinatorial open problem challenging us. Biblio [B-SN09] E. Ben Sasson, J. Nordstrom. A space hierarchy for 
k-DNF Resolution.

 

 

 

(22  Apr) Gianni Franceschini - (La Sapienza DI)

Title: Order Statistic Problems on Suffixes (La Sapienza DI)

Abstract:  

In an Order Statistic Problem we are given a set S of n elements drawn from a total order (U,<) and a rank set R 
of integers drawn from {1,2,...,n}. The objective is to find the k-th smallest element in S for any rank k in R 
(according to the total order (U,<)). Given their basic importance in Computer Science, various instances of 
Order Statistic Problems have been widely studied in the past. Usually, such studies have been carried out
 within the settings of the comparison model and assumed simple unidimensional objects (i.e. comparable in 
O(1) time) as input elements. Probably the most renown results on the subject are the two classic 
papers [Blum, Floyd, Pratt, Rivest, Tarjan, STOC 1972] and [Blum, Floyd, Pratt, Rivest Tarjan, JCSS 7, 1973] 
where the authors established O(n) worst-case time complexities for the median selection and 
generic selection problems. In this talk we focus on Order Statistic Problems on suffixes, that is 
where the input set S contains the suffixes of a given sequence T of n elements (again, drawn from (U,<)). Problems 
on suffixes have practical and theoretical relevance in Computer Science in connection with various fields e.g. 
Text Indexing, Bioinformatics etc. The Suffix Sorting problem has been widely studied in the past and its
 asymptotic complexity is well-known (O(n log n) time in the worst case). This is not the case for 
other fundamental Order Statistic Problems on suffixes, like Generic Suffix Selection, whose asymptotic 
complexity has been unknown until very recently.  In this talk we will focus on the first O(n) time worst-case 
solution to the Generic Suffix Selection Problem (appeared in the paper [Franceschini Muthukrishnan, STOC 2007]). 

 

 

 

(25  Mar) Franco Malvestuto (La Sapienza - DI)

Title: Hypergraph convexity

Abstract: Known properties of "canonical connections" from  database theory and of "closed sets" from 
statistics implicitly define a hypergraph  convexity, here called canonical convexity 
(c-convexity), and provide an efficient algorithm  to compute c-convex hulls. We characterize the 
class of hypergraphs in which c-convexity enjoys  the Minkowski-Krein-Milman property. Moreover, we 
compare c-convexity with the natural extension to hypergraphs of monophonic convexity (or 
m-convexity), and prove that: (1) m-convexity is  coarser than c-convexity, (2) m-convexity and 
c-convexity are equivalent in conformal  hypergraphs, and (3) m-convex hulls can be 
computed in the same efficient way as c-convex  hulls.
Keywords: Finite convexity space;  Minkowski-Krein-Milman property; 

               Acyclic hypergraph; Canonical connection; Monophonic  convexity.

 

(25  Feb) Massimo Lauria (La Sapienza - DI)

Title: Poly-logarithmic independence fools AC0 circuits (reading)

Abstract: Mark Braverman ECCC 2009

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from

the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior

progress on the problem was by Bazzi [Baz07], who showed that O(log^2 n)-independent distributions fool poly-size DNF formulas.

Razborov [Raz08] has later given a much simpler proof for Bazzi's theorem.

 

 

 

 

Fall 2008-2009

 

(26 Jun) Massimo Lauria

Title: Circuit lower bounds by Communication Complexity techniques (reading).

Abstract: Several computational lower bounds have been derived under the  Communication Complexity framework.
Such lower bounds range from VLSI design to data structures, circuit complexity, time-space trade-offs, etc.
In this talk we will show an AC0 circuit which leads to a  communication problem with high complexity.
We will also argue that depth-2 circuits of MAJORITY gates lead to low  complexity communication problems.
This will prove a AC0 cannot be computed by 2-level MAJORITY circuits.
This result relies on a novel technique by A. Sherstov published in STOC 2007.

The talk will start with a reasonably painless introduction of deterministic communication complexity with some
simple examples and applications. Then the probabilistic framework will be introduced, and the main result will be derived.

Finally the proof  of the main theorems will be given.

 

 

(26 Jun) Nicola Galesi

Tecniche di dimostrazioni non sufficienti per risolvere
 "P vs NP" (I_ capitolo): diagonalizzazione e relativizzazione (reading per studenti)

Abstract: Nel seminario presenteremo un risultato classico della Teoria della Complessit_ che, come corollario,

esclude l'uso della tecnica di diagonalizzazione (almeno in certe sue forme generali) per dimostrare

l'esatta relazione tra le classi P (tempo polinomiale) ed NP (tempo polinomiale non deterministico).
Il risultato pu_ essere descritto informalmente come segue: esistono due oracoli A e B tali che

P=NP relativo ad A e P != NP relativo a B.

L'articolo,  "Relativizations of the P =? NP question",  _ di T. Baker, J. Gill e R. Solovay

ed _ pubblicato sul SIAM Journal on Computing, vol (4) del 1975, pp. 431-442,

ed _ ormai presente su tutti i libri moderni di Complessit_ Computazionale.

Nel seminario ricorderemo sia esempi di dimostrazioni per diagonalizzazione

sia la definizione di oracolo.

 

(5 Jun) Silvio Lattanzi 

Random projection trees and low dimensional manifolds  (reading)

Abstract: Sanjoy Dasgupta and Yoav Freund (STOC 2008) www.cse.ucsd.edu/~dasgupta/papers/rptree-tr.pdf

[...]a recent positive development in statistics and machine learning
has been the realization that a lot of data which superficially lies in a
very high-dimensional space R^D, actually has low intrinsic dimension, in
the sense of lying close to a manifold of dimension d; D. There has
thus been a huge interest in algorithms which learn this manifold from
data, with the intention that future data can then be transformed into
this low-dimensional space, in which the usual nonparametric (and other)
methods will work well. [...] In this paper, we are interested in
techniques that automatically adapt to intrinsic low dimensional structure
without having to explicitly learn this structure.

 

 

(29 May) Flavio Chierichetti

Metric Embeddings with Relaxed Guarantees (reading)

 

Abstract:I. Abraham, Y. Bartal, T-H. Chan, K. Dhamdhere, A. Gupta, J. Kleinberg,
O. Neiman, A. Slivkins,
in Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
http://www.cs.cornell.edu/home/kleinber/focs05-slack.pdf
Abstract:
We consider the problem of embedding finite metrics with slack: we seek to produce

embeddings with small dimension and distortion while allowing a (small) constant fraction

of all distances to be arbitrarily distorted. This definition is motivated by recent research in the

networking community which achieved striking empirical success at embedding Internet
latencies with low distortion into low-dimensional Euclidean space, provided that some

small slack is allowed.