I am a graduate student in the
EECS Department
University of California at
Berkeley
My office is in Cory Hall 264 in Wireless
Foundations
Berkeley, CA 94720-1772
Phone no:510-643-9263
Interests |
Publications |
Links |
Resume
Selected Writings on:
Coding for Distributed Systems
Gossip and Message Passing for Sensor Networks
LDPC codes and Pseudocodewords
Game theory
Statistical Signal Processing
I am interested in communications, signal processing and networking
with applications in large-scale distributed systems and sensor networks.
I work with Kannan Ramchandran
and Martin
Wainwright
I am a member of
Wireless Foundations and the BASiCS
research group
I completed my undergraduate studies in
Electrical and Computer Engineering
department
National Technical Univerisity of Athens in 2003.
My advisor was Petros Maragos
I received my Masters from UC Berkeley in 2005 and currently working towards my PhD.
During the summer of 2006 I visited LCAV
in EPFL. I had the pleasure of working with
Martin Vetterli and
Patrick Thiran.
During the summer of 2007 I was with the
Communication and Collaboration Systems group in Microsoft Research.
With Yunnan Wu
we worked on coding for Distributed Storage in Data Centers.
Hobbies
I also like to draw and paint occasionally. Have a look.
Research Publications
What's new:
Coding for Distributed systems
(Preliminary versions appeared in Infocom 2007 and Allerton 2007)
Data centers and sensor networks require reliable information storage
over individually unreliable nodes.
Storing a file using an erasure code, in fragments spread across nodes, requires less redundancy than simple replication for the same level of reliability.
However, since fragments must be periodically replaced as nodes fail, a key question is how to generate a new encoded fragment in a distributed way while
transferring as little data as possible across the network.
For an erasure coded system, a common practice to repair from a node failure is for a new node to download
subsets of data stored at a number of surviving nodes, reconstruct a lost coded block using the downloaded data,
and store it at the new node. We show that this procedure is sub-optimal. We introduce the notion of regenerating
codes, which allow a new node to download functions of the stored data from the surviving nodes. We show that
regenerating codes can significantly reduce the repair bandwidth. Further, we show that there is a fundamental tradeoff
between storage and repair bandwidth which we theoretically characterize using flow arguments on an appropriately
constructed graph. By invoking constructive results in network coding, we introduce regenerating codes that can
achieve any point in this optimal tradeoff.
Gossip (or average Consensus) algorithms, are simple randomized message-passing
algorithms that can be used to compute global functions of data distributed
over a network with minimal coordination.
The proposed gossip algorithm (Geographic Gossip) uses geographic informationto
dramatically improve the convergence time, hence minimizing the number of
communicated messages.
We extend Geographic gossip by allowing all the nodes on a
random path to be averaged and show how this path averaging
can be implemented with minimal complexity in a sensor network
if sensors have location information.
The main result is that Geographic Gossip with path averaging converges
using a number of messages linear in the number of nodes,
which improves by a sqrt(n) factor over geographic gossip and is order-optimal.
Large-scale sensor network applications require in-network processing and data fusion to compute statistically relevant summaries of the sensed measurements. We study distributed message-passing algorithms, in which neighboring nodes in the network pass local information relevant to a global computation, for performing statistical inference. We focus on the class of reweighted belief propagation (RBP) algorithms, which includes as special cases the standard sum-product and max-product algorithms for general networks with cycles, but in contrast to standard algorithms has attractive theoretical properties (uniqueness of fixed points, convergence, and robustness). Our main contribution is to design and implement a practical and modular architecture for implementing RBP algorithms in real networks. In addition, we show how intelligent scheduling of RBP messages can be used to minimize communication between motes and prolong the lifetime of the network. Our simulation and Mica2 mote deployment indicate that the proposed algorithms achieve accurate results despite realworld problems such as dying motes, dead and asymmetric links, and dropped messages. Overall, the class of RBP provides provides an ideal fit for sensor networks due to their distributed nature, requiring only local knowledge and coordination, and little requirements on other services such as reliable transmission.
Abstract: We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses all prior non-asymptotic results for LDPC codes, and in particular exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a generalized matching. An interesting by-product of our analysis is to establish the existence of "probabilistic expanders" i.e. bipartite graphs where almost every (as opposed to every) set (and its subsets) expands, with expansion coefficients much larger than the classical case.
Abstract: A new approach for decoding binary linear codes by solving a linear
program (LP) over a relaxed codeword polytope was recently proposed by
Feldman et al. In this paper we investigate the structure of the
polytope used in the LP relaxation decoding.
This relaxed polytope has
both integral vertices which correspond to codewords and non-integral
vertices called fractional pseudocodewords.
We show that for expander codes, every fractional pseudocodeword
always has at least a constant fraction of non-integral bits.
We also show that codewords have much more facets touching them
relative to fractional pseudocodewords.
Based on these results on the polytope structure, we propose an
decoding algorithm which provably outperforms the
LP decoder for finite blocklengths. The proposed algorithm proceeds
by guessing facets of the polytope and resolving the linear program on
these facets. Guessing facets is a direct generalization of bit guessing
decoders which have been explored in the recent literature.
While the LP decoder succeeds only if the ML codeword
has the highest likelihood over all pseudocodewords, we prove that for
expander codes the proposed algorithm succeeds even with a constant
number of pseudocodewords of higher likelihood. The complexity of the
proposed algorithm is only a constant factor larger than that of the
LP decoder.
We study how the structure of the interaction graph affects the Nash equilibria of the resulting game. In particular, for a fixed interaction graph, we are interested if there exist Nash equilibria which arise when random utility tables are assigned to the players. We provide conditions for the structure of the graph under which equilibria are likely to exist and complementary conditions which make the existence of equilibria highly unlikely. Our results have immediate implications for many deterministic graphs and generalize known results for games on the complete graph. In particular, our results imply that the probability that bounded degree graphs have Nash equilibria is exponentially small in the size of the graph and yield a simple algorithm that finds small non-existence certificates for a large family of graphs. In order to obtain a refined characterization of the degree of connectivity associated with the existence of equilibria, we study the model in the random graph setting. In particular, we look at the case where the interaction graph is drawn from the Erdos-Renyi, G(n,p), model where each edge is present independently with probability p. For this model we establish a double phase transition for the existence of pure Nash equilibria as a function of the average degree p n consistent with the non-monotone behavior of the model. We show that when the average degree satisfies n p > (2 + Omega(1)) log n, the number of pure Nash equilibria follows a Poisson distribution with parameter 1. When 1/n << n p < (0.5 -Omega(1)) log n pure Nash equilibria fail to exist with high probability. Finally, when n p << 1/n a pure Nash equilibrium exists with high probability.
My undergraduate thesis was supervised by Prof. Maragos. We proposed a nonlinear model for time-varying resonances where the instantaneous phase of a sinusoidal oscillation is a self-similar stochastic process. We have theoretically derived the second order statistics of the modulated process for a very general class of Self-similar processes that include Fractional Brownian Motion and Fractional Stable Levy Motion as special cases. We have also applied these ideas to data from fricative phonemes and demonstrated their applicability for speech modelling.
(Copyright belongs to the publisher in most cases. The author/authors assert copyright in all other cases.)
I was the Webmaster of the IEEE Student branch in National Technical University of Athens (NTUA). Visit the
site .
Fun upper bounds: My Erdos Number is less than or equal to 3:
(Paul Erdos-> Noga Alon-> Richard Karp-> myself)
No known finite upper bounds on my Bacon number exist.
Friends
Tasos Argyros
Charis Ermopoulos
Alexandra Meliou
Themos Kallos
Apostolos Fertis
Emmanouil Kioupakis
Victor Panaretos
Konstantinos Daskalakis
Nikolas Geroliminis
Krish Eswaran
Bobak Nazer
Vinod Prabhakaran
Ben Rubinstein
Anand Sarwate