All talks will be at 3:15 pm on Mondays in IST 333 (unless they are part of the departmental colloquium).
If you would like to speak,
please email: theory at cse psu dot edu.
If you want to receive announcements of upcoming talks join the theory mailing list.
A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding
(joint work with Mordecai Golin and Jiajin Yu, published at SODA 2009)
Given a probability distribution over a set of n words to be
transmitted, the Huffman Coding problem is to find a minimal-cost
prefix free code for transmitting those words. The basic Huffman
coding problem can be solved in O(n log n) time but variations are
more difficult. One of the standard techniques for solving these
variations utilizes a top-down dynamic programming approach. In this
paper we show that this approach is amenable to dynamic programming
speedup techniques, permitting a speedup of an order of magnitude for
many algorithms in the literature for such variations as mixed radix,
reserved length and one-ended coding. These speedups are immediate
implications of a general structural property that permits batching
together the calculation of many DP entries.
Coding theory in pseudorandomness: A survey of two recent applications
There is a rich interplay between coding theory and computational
complexity theory that has enriched both disciplines over the
years. In particular, error-correcting codes have been instrumental in
several advances in the subject of pseudorandomness, leading to
explicit constructions of objects (such as expander graphs, randomness
extractors, pseudorandom generators, matrices, etc.) with desirable
properties similar to those achieved by random objects.
This talk will survey recently discovered applications of
coding-theoretic ideas in pseudorandomness, showcasing two examples:
the construction of lossless expanders and randomness extractors from
a variant of Reed-Solomon codes, and the construction of Euclidean
sections and compressed sensing matrices from expander codes.
Tackling the Poor Assumptions of Naive Bayes Text Classifiers
An influential paper by Rennie et al. [1] identified many of the
modeling weaknesses of the Naive Bayes classifier and proposed various
ways of improving the model. One such weakness, the 'skewed data bias'
supposedly causes Naive Bayes to prefer classes with more data points.
We show that the reasoning supporting this claim is flawed and that
experiments also show no significant bias. Instead we show that
variance, not bias is the bigger cause of performance degradation and
we propose a variance reduction technique to improve the performance
of Naive Bayes.
Bibliography
[1] Jason D. Rennie, Lawrence Shih, Jaime Teevan and David R. Karger,
Tackling the Poor Assumptions of Naive Bayes Text Classifiers,
International Conference of Machine Learning 2003.
http://www.cse.psu.edu/~ytyoun/NB/rennie.icml03.pdf
Principal Component Analysis, Singular Value Decompositions and the Random Projection Method
Dimension reduction is a key component of present day data
analysis. Given a data set, one would like to find a small number of
features that capture the most interesting relationships among the
data points. Principal Component Analysis (PCA) is an extremely
efficient tool which helps in dimensionality reduction. The first half
of this talk will define PCA and discuss some applications. In the
second half, we will discuss a randomized algorithm for fast
approximate PCA, based on random projections.
Hard Core Predicates for One Way Functions
I will introduce the concepts of one way functions and
hard core predicates, and in detail I will show the construction and proof
of Goldreich-Levin hard core predicates for one way functions. This topic
is contained in [1] and the exposition in [2] is somewhat easier to
follow.
References:
[1] Goldreich, Foundations of Cryptography. vol 1. chapter 2.
[2] Katz-Lindell, Intro. to Modern Cryptography. chapter 6.
Basic techniques in derandomization
The talk will motivate the problem of finding deterministic versions
of randomized algorithms and illustrate two basic derandomization
techniques: the method of conditional expectations and the generation
of pairwise-independent random variables.
Expander Graphs
Topics to be covered are:
1. Proof of the existence of expanders using probabilistic method;
2. Rapid mixing on expanders;
3. Explicit construction using Zig-zag product.
References:
[1] S. Hoory, N. Linial , and A. Wigderson. "Expander Graphs and
their Applications". Bull. Amer. Math Soc., 43, pp 439--561, 2006
[2] O. Reingold, S. Vadhan, A. Wigderson. "Entropy Waves, The
Zig-Zag Graph Product, and New Constant-Degree Expanders and
Extractors". Proceedings of the 41st FOCS, pp. 3-13, 2000.
Covering by angle sectors
We consider problems of set cover and capacitated set cover where
the elements to be covered are points on Euclidean plane, and sets are
angle sectors of some fixed area, such a set is an intersection of an
angle sector of angle width 1/r with a disk of radius r (both with centers
at the origin).
We show that the minimum set cover can be found in time O(n^4) using space
O(n^2).
In capacitated version of the problem every element has a weight, and a
set used in the cover has to satisfy two conditions:
(a) it is a subset of an explicitely specified set
(b) the sum of weights is at most 1
If we are given an exact solution to an instance of set
cover, and we are also given weights of the elements, we can find an
approximate solution to that capacitated instance with approximation
ratio 2.347.
(Joint work with Karpinski and Lingas, follow-up of joint work with
Jeong, Kasiviswanathan and Urgaonkar.)
Basing Identity Based Encryption on Trapdoor Permutations
Identity-based encryption (IBE) is a special type of public key
encryption scheme where a user's public key is a unique information
about the identity of the user (e.g., a user's email address). Known
constructions of IBE are based on the particular properties of hard
problems in elliptic curves and integer lattices. So it is natural to
ask whether a secure IBE can be constructed from
generic cryptographic primitives. In 2008, Boneh et al. [Bon00] showed
that there is no black-box construction of IBE from trapdoor
permutations (TDP). In this talk, I will explain the actual separation
proof and the meaning of this negative result, along with some topics
in complexity theory such as reduction, oracle, and relativization.
References
[Bon00] Dan Boneh, Periklis A. Papakonstantinou, Charles Rackoff,
Yevgeniy Vahlis, Brent Waters.
On the Impossibility of Basing Identity Based Encryption on Trapdoor
Permutations. FOCS 2008.
Confluence of Learning Theory and Differential Privacy
The talk covers:
1.Some very basic overview of Vapnik-Chervonenkis dimension.
2. Prove the Uniform Convergence Theorem.
3. Use these concepts to design a mechanism to generate a synthetic dataset which preserves some of the important properties of the original dataset
but maintaining differential privacy.
References
1. A Learning Theory Approach to Non-Interactive Database Privacy. Avrim Blum, Katrina Ligett, Aaraon Roth.
2. Mechanism Design via Differential Privacy. Frank McSherry, Kunal Talwar.
3. Calibrating Noise to Sensitivity in Private Data Analysis. Cynthia Dwork,Frank McSherry, Kobbi Nissim, Adam Smith.
Derandomization under complexity assumptions: The Nisan-Wigderson Construction
Abstract:
The fundamental problem that complexity theory addresses is following:
What do we mean by efficiently solvable problem?
Two natural choices for defining such a class have emerged:
P : the class of problems solvable by deterministic algorithms running
in polynomial time, and,
BPP: the class of problems solvable by polynomial time *randomized*
algorithms with bounded error probability.
It is thus natural to ask if these classes coincide, that is, is P = BPP?
It turns out that such a statement can be conditionally proven based
on complexity assumptions. It all started with the seminal work of
Nisan and Wigderson who showed that if there was a function computable
in exponential time that was ``exponentially hard'' for circuits of
slightly less than exponential size, then BPP=P. We will look at their
construction and see the proof of their result.
References:
O. Goldreich.
Computational Complexity: A Conceptual Perspective.
Cambridge University Press, 2008.
N. Nisan and A. Wigderson.
Hardness vs. randomness.
Journal of Computer Systems and Sciences, volume 49,149-167, 1994.
Explicit construction of Expander Graphs using Zig-Zag Product
Abstract:
The talk is going to be on "Explicit construction of Expander Graphs using Zig-Zag Product". The construction was proposed by the paper "Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors" by O. Reingold, S. Vadhan, and A. Wigderson. The construction as well as proof of correctness will be covered in the talk.
Lossy Trapdoor Functions: Applications and Realization
Abstract: Two long-standing problems in cryptography are to construct
trapdoor functions from assumptions not directly related to factoring
and to design chosen ciphertext secure crypto-systems based on
lattices problems. The recent paper [PW08] proposed a new primitive,
called a lossy trapdoor function, and use the idea to solve both
problems. I will introduce this new notion and give the construction
of trapdoor functions and collision-resistant hash functions based on
it. Finally, I will show how to realize lossy trapdoors from the DDH
assumption.
References:
1] Chris Peikert, Brent Waters: Lossy trapdoor functions and their
applications. STOC 2008
[2] Oded Regev: On lattices, learning with errors, random linear
codes, and cryptography. STOC 2005