BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Manjish Pal

Manjish Pal contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational ComplexityComputational GeometryDatabasesDiscrete Mathematicsmath.COmath.MGNetworking and Internet ArchitectureSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
9topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2015arXiv

Evolving Social Networks via Friend Recommendations

A social network grows over a period of time with the formation of new connections and relations. In recent years we have witnessed a massive growth of online social networks like Facebook, Twitter etc. So it has become a problem of extreme importance to know the destiny of these networks. Thus predicting the evolution of a social network is a question of extreme importance. A good model for evolution of a social network can help in understanding the properties responsible for the changes occurring in a network structure. In this paper we propose such a model for evolution of social networks. We model the social network as an undirected graph where nodes represent people and edges represent the friendship between them. We define the evolution process as a set of rules which resembles very closely to how a social network grows in real life. We simulate the evolution process and show, how starting from an initial network, a network evolves using this model. We also discuss how our model can be used to model various complex social networks other than online social networks like political networks, various organizations etc..

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fast Approximate Matrix Multiplication by Solving Linear Systems

In this paper, we present novel deterministic algorithms for multiplying two $n \times n$ matrices approximately. Given two matrices $A,B$ we return a matrix $C'$ which is an \emph{approximation} to $C = AB$. We consider the notion of approximate matrix multiplication in which the objective is to make the Frobenius norm of the error matrix $C-C'$ arbitrarily small. Our main contribution is to first reduce the matrix multiplication problem to solving a set of linear equations and then use standard techniques to find an approximate solution to that system in $\tilde{O}(n^2)$ time. To the best of our knowledge this the first examination into designing quadratic time deterministic algorithms for approximate matrix multiplication which guarantee arbitrarily low \emph{absolute error} w.r.t. Frobenius norm.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sixsoid: A new paradigm for $k$-coverage in 3D Wireless Sensor Networks

Coverage in 3D wireless sensor network (WSN) is always a very critical issue to deal with. Coming up with good coverage models implies more energy efficient networks. $K$-coverage is one model that ensures that every point in a given 3D Field of Interest (FoI) is guaranteed to be covered by $k$ sensors. When it comes to 3D, coming up with a deployment of sensors that gurantees $k$-coverage becomes much more complicated than in 2D. The basic idea is to come up with a geometrical shape that is guaranteed to be $k$-covered by taking a specific arrangement of sensors, and then fill the FoI will non-overlapping copies of this shape. In this work, we propose a new shape for the 3D scenario which we call a \textbf{Devilsoid}. Prior to this work, the shape which was proposed for coverage in 3D was the so called \textbf{Reuleaux Tetrahedron}. Our construction is motivated from a construction that can be applied to the 2D version of the problem \cite{MS} in which it imples better guarantees over the \textbf{Reuleaux Triangle}. Our contribution in this paper is twofold, firstly we show how Devilsoid gurantees more coverage volume over Reuleaux Tetrahedron, secondly we show how Devilsoid also guarantees simpler and more pragmatic deployment strategy for 3D wireless sensor networks. In this paper, we show the constuction of Devilsoid, calculate its volume and discuss its effect on the $k$-coverage in WSN.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Maximum Matchings via Glauber Dynamics

In this paper we study the classic problem of computing a maximum cardinality matching in general graphs $G = (V, E)$. The best known algorithm for this problem till date runs in $O(m \sqrt{n})$ time due to Micali and Vazirani \cite{MV80}. Even for general bipartite graphs this is the best known running time (the algorithm of Karp and Hopcroft \cite{HK73} also achieves this bound). For regular bipartite graphs one can achieve an $O(m)$ time algorithm which, following a series of papers, has been recently improved to $O(n \log n)$ by Goel, Kapralov and Khanna (STOC 2010) \cite{GKK10}. In this paper we present a randomized algorithm based on the Markov Chain Monte Carlo paradigm which runs in $O(m \log^2 n)$ time, thereby obtaining a significant improvement over \cite{MV80}. We use a Markov chain similar to the \emph{hard-core model} for Glauber Dynamics with \emph{fugacity} parameter $λ$, which is used to sample independent sets in a graph from the Gibbs Distribution \cite{V99}, to design a faster algorithm for finding maximum matchings in general graphs. Our result crucially relies on the fact that the mixing time of our Markov Chain is independent of $λ$, a significant deviation from the recent series of works \cite{GGSVY11,MWW09, RSVVY10, S10, W06} which achieve computational transition (for estimating the partition function) on a threshold value of $λ$. As a result we are able to design a randomized algorithm which runs in $O(m\log^2 n)$ time that provides a major improvement over the running time of the algorithm due to Micali and Vazirani. Using the conductance bound, we also prove that mixing takes $Ω(\frac{m}{k})$ time where $k$ is the size of the maximum matching.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Entropy Influence Conjecture Revisited

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$ satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96). The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of the function. The conjecture has been proven for families of functions of smaller sizes. O'donnell, Wright and Zhou (ICALP'11) verified the conjecture for the family of symmetric functions, whose size is $2^{n+1}$. They are in fact able to prove the conjecture for the family of $d$-part symmetric functions for constant $d$, the size of whose is $2^{O(n^d)}$. Also it is known that the conjecture is true for a large fraction of polynomial sized DNFs (COLT'10). Using elementary methods we prove that a random function with high probability satisfies the conjecture with the constant as $(2 + δ)$, for any constant $δ> 0$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Combinatorial Geometry of Graph Partitioning - I

The {\sc $c$-Balanced Separator} problem is a graph-partitioning problem in which given a graph $G$, one aims to find a cut of minimum size such that both the sides of the cut have at least $cn$ vertices. In this paper, we present new directions of progress in the {\sc $c$-Balanced Separator} problem. More specifically, we propose a family of mathematical programs, that depend upon a parameter $p > 0$, and is an extension of the uniform version of the SDPs proposed by Goemans and Linial for this problem. In fact for the case, when $p=1$, if one can solve this program in polynomial time then simply using the Goemans-Williamson's randomized rounding algorithm for {\sc Max Cut} \cite{WG95} will give an $O(1)$-factor approximation algorithm for {\sc $c$-Balanced Separator} improving the best known approximation factor of $O(\sqrt{\log n})$ due to Arora, Rao and Vazirani \cite{ARV}. This family of programs is not convex but one can transform them into so called \emph{\textbf{concave programs}} in which one optimizes a concave function over a convex feasible set. It is well known that the optima of such programs lie at one of the extreme points of the feasible set \cite{TTT85}. Our main contribution is a combinatorial characterization of some extreme points of the feasible set of the mathematical program, for $p=1$ case, which to the best of our knowledge is the first of its kind. We further demonstrate how this characterization can be used to solve the program in a restricted setting. Non-convex programs have recently been investigated by Bhaskara and Vijayaraghvan \cite{BV11} in which they design algorithms for approximating Matrix $p$-norms although their algorithmic techniques are analytical in nature.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

On Low Distortion Embeddings of Statistical Distance Measures into Low Dimensional Spaces

Statistical distance measures have found wide applicability in information retrieval tasks that typically involve high dimensional datasets. In order to reduce the storage space and ensure efficient performance of queries, dimensionality reduction while preserving the inter-point similarity is highly desirable. In this paper, we investigate various statistical distance measures from the point of view of discovering low distortion embeddings into low-dimensional spaces. More specifically, we consider the Mahalanobis distance measure, the Bhattacharyya class of divergences and the Kullback-Leibler divergence. We present a dimensionality reduction method based on the Johnson-Lindenstrauss Lemma for the Mahalanobis measure that achieves arbitrarily low distortion. By using the Johnson-Lindenstrauss Lemma again, we further demonstrate that the Bhattacharyya distance admits dimensionality reduction with arbitrarily low additive error. We also examine the question of embeddability into metric spaces for these distance measures due to the availability of efficient indexing schemes on metric spaces. We provide explicit constructions of point sets under the Bhattacharyya and the Kullback-Leibler divergences whose embeddings into any metric space incur arbitrarily large distortions. We show that the lower bound presented for Bhattacharyya distance is nearly tight by providing an embedding that approaches the lower bound for relatively small dimensional datasets.

0 citations0 reviewsNo code linkedOpen access