-
20 Feb 2012 at 12:15 in room 1537
Secure and insecure mixing
(Shahram Khazaei, KTH CSC)
A mix-net, first introduced by Chaum in 1981, is a tool to provide
anonymity for a group of senders. The main application is electronic
voting, in which each sender submits an encrypted vote and the mix-net
then outputs the votes in sorted order. This talk is divided in two
parts. First, I present our results on mix-nets with randomized partial
checking (RPC), a heuristic protocol proposed by Jakobsson, Juels, and
Rivest (2002). We identify serious issues in the original description of
mix-nets with RPC and show how to exploit these to break both correctness
and privacy. Our attacks are practical and applicable to real world mix-net
implementations including Scantegrity, developed by a team of researchers
including Chaum and Rivest. We can replace the complete output without
detection. In the second part, I will describe a provably secure mix-net
called TWT (trip-wire tracing). TWT is the first provably secure mix-net
that can be based on any CCA2 secure cryptosystem. It is fairly efficient
and uses no zero-knowledge proofs at all.
The first part is a joint work with Douglas Wikström and the second
part is a joint work with Tal Moran and Douglas Wikström.
-
13 Feb 2012 at 13:15 in room 1537
The SAT Problem and Boolean Gröbner Bases
(Samuel Lundqvist, Stockholm University)
The Stone transformation interprets a Boolean formula as a set of
polynomials with coefficients in F_2. I will explain how this set of
polynomials can be analyzed in order to determine if the original Boolean
formula is satisfiable. The talk is intended for computer scientists who
are familiar with the SAT problem.
The seminar will be 2 x 45 minutes with a 15 minute break.
-
30 Jan 2012 at 13:15 in room 1537
Width-parameterized SAT: Time-Space Tradeoffs
(Bangsheng Tang, Tsinghua University)
Width parameterizations of SAT, such as tree-width and path-width,
enable the study of computationally more tractable and practical SAT
instances. We give two simple algorithms. One that runs simultaneously
in time-space $(O^*(2^{2tw(\phi)}), O^*(2^{tw(\phi)}))$ and another that
runs in time-space $(O^*(3^{tw(\phi)\log{|\phi|}}),|\phi|^{O(1)})$,
where $tw(\phi)$ is the tree-width of a formula $\phi$ with $|\phi|$
many clauses and variables. This partially answers the question of
Alekhnovitch and Razborov, who also gave algorithms exponential both
in time and space, and asked whether the space can be made smaller.
We conjecture that every algorithm for this problem that runs in time
$2^{tw(\phi)\mathbf{o(\log{|\phi|})}}$ necessarily blows up the space to
exponential in $tw(\phi)$.
We introduce a novel way to combine the two simple algorithms that allows
us to trade \emph{constant} factors in the exponents between running time
and space. Our technique gives rise to a family of algorithms controlled
by two parameters. By fixing one parameter we obtain an algorithm that
runs in time-space $(O^*(3^{1.441(1-\epsilon)tw(\phi)\log{|\phi|}}),
O^*(2^{2\epsilon tw(\phi)}))$, for every $0<\epsilon<1$. We
systematically study the limitations of this technique, and show that these
algorithmic results are the best achievable using this technique.
We also study further the computational complexity of width
parameterizations of SAT. We prove non-sparsification lower bounds for
formulas of path-width $\omega(\log|\phi|)$, and a separation between the
complexity of path-width and tree-width parametrized SAT modulo plausible
complexity assumptions.
This is joint work with Eric Allender, Shiteng Chen, Tiancheng Lou,
Periklis Papakonstantinou.
-
23 Jan 2012 at 13:15 in room 1537
Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space
(Christopher Beck, Princeton University)
For modern SAT solvers based on DPLL with clause learning, the two major
bottlenecks are the time and memory used by the algorithm. This raises
the question of whether this memory bottleneck is inherent to Resolution
based approaches, or an artifact of the particular search heuristics
currently used in practice? There is a well known correspondence between
these algorithms and the Resolution proof system, in which these resources
correspond to the length and space of proofs. While every tautology has a
linear-space proof, this proof is in general of exponential size, raising
the issue of size-space tradeoffs: perhaps, in high space, there is a short
proof, but with constrained space only much longer proofs exist. Space
complexity and time-space tradeoffs have been the subject of much recent
work in proof complexity, but until this work, no such bound applied to
super-linear amounts of space.
We obtain strong time-space tradeoff lower bounds for a simple and explicit
collection of formulas - in particular for any k, we give a sequence of
formulas of length n such that with n^k space there is a proof of length
polynomial in n, but for which every proof is superpolynomial when the
space is constrained to n^{k/2}. Thus, on these instances, if you want to
run in polynomial time, you need a large polynomial amount of space.
Joint work with Paul Beame and Russell Impagliazzo.
The seminar will be about 45-60 minutes and does not require any prior
knowledge of proof complexity.
-
03 Jan 2012 at 13:15 in room 1537
An Epistemic Approach to Mechanism Design
(Rafael Pass, Cornell University)
We introduce an epistemic framework for analyzing mechanisms. This
framework enables mechanism designers to define desirability of outcomes
not only based on players' actual payoff types and their beliefs about
the payoff types of other players (as in the classic models), but also
based on higher order beliefs of the players (i.e., beliefs about beliefs
about ... the payoff types of the players). In this framework, we may also
use epistemic solution concepts to analyze what outcomes are consistent
with different levels of rationality: a player is k-level rational if
he is rational and considers all other players (k-1)-level rational;
following Aumann, we consider a very weak notion of rationality: player i
is *rational* if he uses a strategy \sigma such that for every alternative
strategy \sigma', i considers some world possible where \sigma performs at
least as well as \sigma'.
We showcase this framework in the context of single-good auctions,
presenting an interim individually-rational mechanism with the following
revenue guarantee: for any k\geq 0, any outcome consistent with all
players being (k+1)-level rational guarantees the seller a revenue of G^k
- \epsilon (for any \epsilon > 0), where G^k is the second highest
belief about belief about ... (k times) about the highest valuation of
some player. We additionally show that no interim individually rational
mechanism can guarantee a revenue of G^k - \epsilon for any constant
\epsilon, if only assuming players are k-level rational (as opposed to
(k+1)-level rational). Taken together, these results demonstrate the
existence of a ``revenue-rationality hierarchy'': strictly higher revenue
may be extracted by assuming players satisfy higher levels of rationality.
Towards analyzing our mechanism and proving our lower bounds, we introduce
an iterative deletion procedure of dominated strategies that precisely
characterizes strategies consistent with k-level rationality.
Prior knowledge of mechanism design or epistemic logic will not be assumed.
Joint work with Jing Chen and Silvio Micali.
-
15 Dec 2011 at 10:15 in room 1537
Modern SAT Solving: CDCL and Inprocessing
(Matti Järvisalo, University of Helsinki)
Boolean satisfiability (SAT) has become an attractive approach to
solving hard decision and optimization problems arising from artificial
intelligence, knowledge representation, and various industrially relevant
domains. The success of the SAT-based approach relies heavily on the
development of increasingly robust and efficient SAT solvers. This talk
gives a two-part overview of the current state-of-the-art SAT solver
technology based on the conflict-driven clause learning (CDCL) paradigm.
In the first part, I will provide a basic overview of the most important
components of CDCL SAT solvers today. The second part of the talk
concentrates on the important aspect of practical preprocessing for SAT and
the inprocessing SAT solving paradigm in which more extensive reasoning is
interleaved with the core satisfiability search (not only before search). I
will review some of the most successful SAT preprocessing techniques, and
give an overview of our recent work (joint work with Armin Biere and Marijn
Heule) on developing new reasoning techniques for pre- and inprocessing.
The seminar will be 2*45 minutes with a 15 minute break.
-
07 Dec 2011 at 13:15 in room 1537
An additive combinatorics approach to the log-rank conjecture in communication complexity
(Noga Zewi, Technion, Haifa)
For a {0,1}-valued matrix M let CC(M) denote he deterministic communication
complexity of the boolean function associated with M. The log-rank
conjecture of Lovasz and Saks [FOCS 1988] states that CC(M) <=
log^c(rank(M)) for some absolute constant c where rank(M) denotes the rank
of M over the field of real numbers.
We show that CC(M) <= c rank(M)/ logrank(M) for some absolute constant
c, assuming a well-known conjecture from additive combinatorics, known as
the Polynomial Freiman-Ruzsa (PFR) conjecture.
Our proof is based on the study of the "approximate duality conjecture"
which was recently suggested by Ben-Sasson and Zewi [STOC 2011] and
studied there in connection to the PFR conjecture. First we improve the
bounds on approximate duality assuming the PFR conjecture. Then we use
the approximate duality conjecture (with improved bounds) to get the
aforementioned upper bound on the communication complexity of low-rank
martices, and this part uses the methodology suggested by Nisan and
Wigderson [Combinatorica 1995].
Joint work with Eli Ben-Sasson and Shachar Lovett.
The talk will be 2*45 minutes with the first 45 minutes intended for a
general audience.
-
05 Dec 2011 at 13:15 in room 1537
Robust set-valued prediction in games
(Jörgen Weibull, Handelshögskolan, Stockholm)
Game theory has transformed economics and greatly influenced other social
and behavioral sciences. The central solution concept used in applications
is that of Nash equilibrium. Yet Nash equilibria can be fragile and Nash
equilibrium play does not generally follow from assumptions of rationality
or of evolution. It is here argued that an exploration of methods for
robust set-valued prediction in games is called for, and some such
approaches and avenues for future research are discussed.
-
24 Nov 2011 at 13:15 in room 4523
Integrity Protection for Authorized Changes - Sanitizable Signatures with Transparency or Detectability
(Heinrich Pöhls, University of Passau, Germany)
Sanitizable Signature Schemes enhance Digital Signatures by allowing the
signer to allow a third-party called the sanitizer to make authorized
changes to signed document. I will introduce our newest results on
re-definition of the security properties Transparency and Detectability
for Sanitizable Signatures. Transparency has been defined already by G.
Ateniese, D. H. Chou, B. de Medeiros, and G. Tsudik in their 2005 ESORIC's
paper titled "Sanitizable signatures". Transparency in a nutshell means
that a verifier cannot distinguish with a probability better than 0.5
between a sanitized and an original version of a signed document.
We have introduced and formalized the notion of detectability, which
captures that a verifier will always be able to detect a sanitization.
This still allows an authorized change to be verified, but it becomes
detectable. In this talk I will explain the security properties of
sanitizable signatures and show some applications. Finally, I will
introduce the legal implications of transparency, which we circumvent by
using a detectable sanitizable signature scheme.
-
14 Nov 2011 at 13:15 in room 4523
Sampling Massive Online Graphs: Challenges, Techniques, and Applications to Facebook
(Maciej Kurant, University of California, Irvine)
Online Social Networks (OSNs) have recently emerged as a new killer
application, and are of interest to a number of communities, ranging from
computer science and engineering to social sciences. Because of their sheer
size (Facebook alone has more than 800 million active users), OSNs are
widely studied today based on *samples* collected through measurements of
publicly available information. In this talk, I will give an overview of
our recent work on sampling OSNs.
First, I will discuss how to efficiently crawl a friendship graph to
collect a representative sample of its *nodes*. To this end, I will
introduce two novel techniques: (i) "Multigraph Sampling" that exploits
different relations between nodes, and (ii) "Stratified Weighted Random
Walk" that preferentially crawls nodes more relevant to our measurement.
I will evaluate these techniques on real-life OSNs, such as Facebook and
LastFM. This will also allow me to study some basic characteristics of
these OSNs, e.g., the privacy awareness in Facebook.
Second, I will focus on *topology* rather than on nodes alone. Breadth
First Search (BFS) is a natural and widely used sampling technique in
this context. Unfortunately, BFS is subject to nontrivial and often very
significant biases, which I quantify analytically. As a viable alternative,
I propose to study a "coarse-grained" version of the underlying topology,
and I show how to estimate it based on a sample of nodes. Finally, I will
apply this methodology to Facebook to obtain a global country-to-country
friendship network (more examples available at geosocialmap.com).
This work is joint with Athina Markopoulou, Minas Gjoka, and Carter Butts
at the University of California, Irvine and with Patrick Thiran at EPFL,
Lausanne. Parts of this work appear in IEEE INFOCOM 2010, ITC 2010, ACM
SIGMETRICS 2011 and IEEE JSAC 2011.
-
24 Oct 2011 at 13:15 in room 1537
The Landscape of Structural Graph Parameters
(Michail Lampis, KTH CSC)
In traditional computational complexity we measure algorithm running times
as functions of one variable, the size of the input. Though in this setting
our goal is usually to design polynomial-time algorithms, most interesting
graph problems are unfortunately believed to require exponential time to
solve exactly.
Parameterized complexity theory refines this by introducing a second
variable, called the parameter, which is supposed to quantify the
“hardness” of each specific instance. The goal now becomes
to confine the combinatorial explosion to the parameter, by designing an
algorithm that runs in time polynomial in the size of the input, though
inevitably exponential in the parameter. This will allow us to tackle
instances where the parameter value is much more modest than the input
size, which will happen often if the parameter is chosen well.
Of course, this setting is rather general and there are countless ways
in which one may attempt to measure the hardness of specific instances,
depending on the problem. The parameterized graph algorithms literature
has been dominated for a long time by a very successful notion called
treewidth, which measures graph complexity by quantifying a graph's
similarity to a tree. However, more recently the study of alternative graph
parameters and widths has become more popular. In this (self-contained)
talk we will attempt to explore the algorithmic properties of treewidth,
its related graph width parameters, as well as other graph invariants
which may serve as measurements of a graph's complexity such as Vertex
Cover, or Max-Leaf number. We will focus especially on general results
which prove tractability for whole classes of problems characterized by
expressibility in certain logics, results often referred to as "algorithmic
meta-theorems".
-
10 Oct 2011 at 13:15 in room 1537
An Anonymity Framework for SaaS
(Ricardo Puttini, University of Brasília)
Cloud computing technology has recently experienced rapid growth and
continuous adoption. Enterprises are evermore taking advantage of its
dynamicity and ubiquity. However, migrating strategic services to the cloud
has put embracing companies in a fragile spot. Entrusting key business
knowledge to cloud service providers and consequently relinquishing any
claims to complete privacy is the tradeoff applied to adopters of the
technology. This happens because the cloud computing service model called
SaaS (Software as a Service) makes use of service contracts that inherently
give the service provider access to unreasonable amounts of information
regarding the consumer’s business. The service consumer has, then, no
option but to trust the service provider. Because of that, there emerges a
demand for a reliable, private and economically viable framework for cloud
service consumption.
Our contribution unfolds as a privacy aware environment for cloud service
consumption with a payment mechanism for maintaining the commercially
feasibility of the SaaS service model. Regarding the supporting of privacy,
anonymity techniques are employed both in service contract and network
levels. As for the payment methods, encryption algorithms in the area of
blind signatures complete the proposed framework.
-
27 Sep 2011 at 10:15 in room 1537
Increasing availability in a p2p storage system through a truthful taxation mechanism
(Krzysztof Rzadca, University of Warsaw, Poland)
In peer-to-peer storage systems, peers replicate each others' data in order
to increase availability. If the matching is done centrally, the algorithm
can optimize data availability in an equitable manner for all participants.
However, if matching is completely decentralized, peers' selfishness can
greatly alter the results, leading to performance inequities that can
render the system unreliable and thus ultimately unusable.
In this presentation, we show game-theoretic mechanisms that reduce
the price of anarchy, i.e., the relative loss of efficiency in the
decentralized matching scenario. The mechanism "taxes" the highly-available
peers. A fraction of their replication slots is used by a centralized
algorithm to replicate data of weakly-available peers. We prove the
conditions under which the mechanism is incentive-compatible, i.e., no peer
gains by artificially lowering its availability. We also experimentally
show that the mechanism renders the system usable, as the data availability
of weakly-available peers increases by approximately two orders of
magnitude.
-
26 Sep 2011 at 16:15 in room 1537
Codes tailor-made for distributed networked storage
(Anwitaman Datta, NTU Singapore)
Redundancy is essential for fault-tolerance in distributed networked
storage systems – which are ubiquitous and come in diverse
flavors (e.g., p2p storage, data-centers). Erasure codes provide
orders of magnitude better performance than replication in terms of
fault-tolerance/storage overhead trade-offs, however traditional erasure
codes incur high overhead for recreating lost redundancy in the system.
This cardinal drawback has led to a recent flurry in designing codes which
are tailor-made with the nuances of distributed storage systems in mind. In
this talk, we will provide a brief overview of some such proposed codes,
concluding with self-repairing codes.
More details can be found at:
http://sands.sce.ntu.edu.sg/CodingForNetworkedStorage/
-
19 Sep 2011 at 13:15 in room 4523
A little advice can be very helpful
(Arkadev Chattopadhyay, University of Toronto)
Proving superpolylogarithmic lower bounds for dynamic data structures has
remained an open problem despite years of research. Recently, Patrascu
proposed an exciting new approach for breaking this barrier via a two
player communication model in which one player gets private advice at the
beginning of the protocol. He gave reductions from the problem of solving
an asymmetric version of set-disjointness in his model to a diverse
collection of natural dynamic data structure problems in the cell probe
model. He also conjectured that, for any hard problem in the standard
two-party communication model, the asymmetric version of the problem is
hard in his model, provided not too much advice is given.
We prove several surprising results about his model. We show that there
exist Boolean functions requiring linear randomized communication
complexity in the two-party model, for which the asymmetric versions in
Patrascu's model have deterministic protocols with exponentially smaller
complexity. For set-disjointness, which also requires linear randomized
communication complexity in the two-party model, we give a deterministic
protocol for the asymmetric version in his model with a quadratic
improvement in complexity. These results demonstrate that Patrascu's
conjecture, as stated, is false. In addition, we show that the randomized
and deterministic communication complexities of problems in his model
differ by no more than a logarithmic multiplicative factor.
We also prove lower bounds in some restricted versions of this model for
natural functions such as set-disjointness and inner product. All of our
upper bounds conform to these restrictions.
This is joint work with J. Edmonds, F. Ellen and T. Pitassi.
-
16 Sep 2011 at 10:15 in room 1537
How Unique and Traceable are Usernames?
(Daniele Perito, INRIA, France)
Usernames are ubiquitously used for identification and authentication
purposes on web services and the Internet at large, ranging from the
local-part of email addresses to identifiers in social networks. Usernames
are generally alphanumerical strings chosen by the users and, by design,
are unique within the scope of a single organization or web service. In
this paper we investigate the feasibility of using usernames to trace or
link multiple profiles across services that belong to the same individual.
The intuition is that the probability that two usernames refer to the
same physical person strongly depends on the “entropy” of the
username string itself. Our experiments, based on usernames gathered from
real web services, show that a significant portion of the users’
profiles can be linked using their usernames. In collecting the data needed
for our study, we also show that users tend to choose a small number of
related usernames and use them across many services. To the best of our
knowledge, this is the first time that usernames are considered as a source
of information when profiling users on the Internet.
-
12 Sep 2011 at 13:15 in room 1537
Algorithmic analysis and complexity lower bounds
(Rahul Santhanam, University of Edinburgh)
I will discuss some connections between analysis of algorithms for
satisfiability and complexity lower bound techniques. First I will present
an algorithm for Formula-SAT which runs in time 2^{n-\Omega(n)} on formulae
of linear size. The analysis of the algorithm relies on the method of
random restrictions, originally used to prove formula size lower bounds.
Then I will sketch a connection between the Neciporuk lower bound technique
in concrete complexity and the algorithmic technique of memoization. If
time permits, I will show that the published analyses of some well-known
algorithms for satisfiability are tight, and pose some questions about
further connections in this vein.
-
05 Sep 2011 at 13:15 in room 1537
Hardness amplification for polynomial threshold proof systems
(Trinh Huynh, University of Washington)
Using known results from multiparty number-on-forehead communication
complexity, we exhibit a simple hardness amplification method that converts
any t-CNF formula of large rank complexity in Resolution, for constant
t, into a new related formula requring large rank and tree-like size
complexity in much stronger proof systems, namely polynomial threshold
proof systems, which consist of all systems for proving propositional
tautologies by manipulating degree-k polynomial inequalities (collectively
denoted as Th(k) proof systems). This method works for any k<loglog
n, where n is the size of the formula. These include Gomory-Chvatal
cutting-planes (CP) (as a special case of Th(1)) and Lovasz-Schrijver
systems (as special cases of Th(2)). This method thus yields new rank and
tree-like size lower bounds for a large number of natural formulas in these
systems, whereas previously, lower bounds for only a handful of problems
were known.
For every even constant t>5, we also obtain strong integrality gap
results for the MAX-t-SAT problem for Th(1) systems, which include CP. We
also show that Th(k) systems are strictly stronger than Th(k-1) systems,
for every k<loglog n, in terms of rank and tree-like size.
This is joint work with Paul Beame and Toniann Pitassi.
-
22 Aug 2011 at 15:30 in room 1537
Monotonicity testing and shortest-path routing on the cube
(Arie Matsliah, IBM Haifa Research Laboratory and Technion - Israel Institute of
Technology)
How many edges does one need to remove from a directed n dimensional cube
to disconnect t disjoint source-sink vertex pairs? We show a construction
where removing t/\sqrt{n} edges suffices. This answers a decade-old
question of Lehman and Ron related to monotonicity testing, and gives a
stronger counterexample to Szymanski's conjecture on hypercube routing.
The presentation is self-contained and elementary.
Based on a joint work with Jop Briet, Sourav Chakraborty and David
Garcia-Soriano.
