User suresh venkat - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:43:30Z http://mathoverflow.net/feeds/user/972 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79419/exponential-or-other-families-of-distributions-on-manifolds Exponential (or other) families of distributions on manifolds. Suresh Venkat 2011-10-28T17:53:30Z 2013-03-11T10:22:39Z <p>The <a href="http://en.wikipedia.org/wiki/Exponential_family" rel="nofollow">exponential</a> family is a general parametrized class of probability distributions on $R^n$ that has many nice properties (ML estimation among them) and includes most of the "standard" distributions one encounters (Gaussian, multinomial, exponential, $\chi^2$ etc).</p> <p>Are there similarly well-defined parametrized families of distributions for <em>manifold</em>-valued random variables ? Specifically, if you have a general Riemannian manifold ? Or asked another way, is there an equivalent notion of an "exponential family" for a Riemannian manifold ? </p> http://mathoverflow.net/questions/114879/an-optimization-problem-non-complete-bipartite-graph-and-hungarian-algorithm/114954#114954 Answer by Suresh Venkat for An optimization problem, non complete bipartite graph and hungarian algorithm Suresh Venkat 2012-11-30T04:25:03Z 2012-11-30T04:25:03Z <p>There's a standard trick to convert the min cost matching problem on a balanced bipartite graph to one on an unbalanced bipartite graph. Let $G = (X \cup Y, E, w)$ be the bipartite graph where $E \subset X \times Y$ and $|X| \le |Y|$. </p> <p>Now create a copy of $G$ and add it "reversed", so that in the new graph both sides have exactly $|X| + |Y|$ vertices. All old edges have their same weight: edges between vertices in $X$ and their copies have weight $\infty$, and edges between vertices in $Y$ and their copies have weight zero. </p> <p>Now run the usual algorithm, and the solution will have cost exactly twice the unbalanced cost. </p> <p>p.s the fact that the graph is not complete is irrelevant - you can always pretend that there are dummy edges with infinite weight. </p> <p>While the above method works, it's inefficient. there's a <a href="http://www.hpl.hp.com/techreports/2012/HPL-2012-40.pdf" rel="nofollow">recent (2012) paper by Ramshaw and Tarjan</a> on exactly this problem. </p> http://mathoverflow.net/questions/112626/2-coloring-a-planar-hypergraph 2-Coloring a planar hypergraph Suresh Venkat 2012-11-17T00:10:47Z 2012-11-17T09:10:25Z <p>Consider a hypergraph (of rank 3) $H = (V, E)$ (where the rank of $H$ is the maximum cardinality of a hyperedge). $H$ is said to be planar if we can construct a planar graph $G = (V, A)$, and a mapping $f$ from $E$ to the faces of $G$ such that $v \in E$ iff $v$ is adjacent to $f(E)$ in the drawing. </p> <p>Further, a hypergraph is said to be 2-colorable if there is an assignment of the colors R, B to the vertices so that no edge is monochromatic. </p> <p><a href="http://www.cs.elte.hu/~lovasz/scans/covercolor.pdf" rel="nofollow">It is known that $2$-coloring a hypergraph of rank 3 is NP-complete</a>. </p> <p>Is there anything known about the complexity of 2-coloring a <em>planar</em> hypergraph of rank 3 ? </p> http://mathoverflow.net/questions/92620/known-graph-surface-invariants-that-can-be-extracted-from-homology-over-different Known graph/surface invariants that can be extracted from homology over different fields Suresh Venkat 2012-03-29T22:34:31Z 2012-03-30T20:02:01Z <p>The $Z_2$-homology of a surface viewed as a simplicial complex allows us to extract interesting invariants from the resulting homology groups. $\beta_0$ is the number of connected components, $\beta_1$ is the number of "tunnels" and $\beta_2$ is the number of "cavities" ($\beta_i$, the $i^{th}$ Betti number, being the rank of the $i^{th}$ homology group)</p> <p>Are there other "interesting" invariants of surfaces (or even graphs) that can be obtained by going from $Z_2$ to some other field (like the rationals), or are all of these equivalent in some sense ? </p> http://mathoverflow.net/questions/84305/finding-optimal-vertex-partitioning-of-graphs-to-maximize-cohesion-and-minimize-c/84362#84362 Answer by Suresh Venkat for Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling Suresh Venkat 2011-12-27T04:49:39Z 2011-12-27T04:49:39Z <p>I'm not sure where in your formulation you use the directed nature of the graphs. However, if that's not a critical point, correlation clustering is a clean formulation that captures this: You're given a weighted graph and the goal is to find a partitioning so that you maximize (the sum of weights for intra0cluster edges - sum of weights of intercluster edges). There are simple approximation algorithms for this problem (<a href="http://www.cs.yale.edu/homes/el327/papers/CorrelationClusteringRevisited.pdf" rel="nofollow">see the references here</a>)</p> http://mathoverflow.net/questions/16534/different-ways-of-proving-that-two-sets-are-equal Different ways of proving that two sets are equal Suresh Venkat 2010-02-26T18:09:42Z 2011-08-08T21:08:35Z <p><em>I'm not sure if this is a soft question, or should be community wiki.</em> </p> <p>I was explaining to a student how to prove that two sets were equal using what I called the 'oldest trick in the book': to show that $A = B$, prove $A \subseteq B$ and $B \subseteq A$. This got me thinking: what <strong>are</strong> the other ways of showing that two sets are equal. There's of course the bijection method (establish a 1-1 onto correspondence), but I couldn't think of others off the top of my head. </p> <p>Are there many more general-ish techniques for proving two sets equal ? </p> http://mathoverflow.net/questions/55453/finding-numbers-at-k-hamming-distance/55494#55494 Answer by Suresh Venkat for finding numbers at k hamming distance Suresh Venkat 2011-02-15T08:10:48Z 2011-02-15T08:10:48Z <p>If you're willing to live with approximations, then the standard approach to near-neighbor search (or in your case fixed radius search) in a Hamming space is by using <a href="http://www.mit.edu/~andoni/LSH/" rel="nofollow">locality-sensitive hashing</a>. Your case is even simpler because you know the radius you're concerned with. Alternatives include the method by <a href="http://www.cs.technion.ac.il/~rabani/pss/Publications/KushilevitzOR98.ps.gz" rel="nofollow">Kushilevitz, Ostrovsky and Rabani</a>. </p> http://mathoverflow.net/questions/54146/analogy-of-parseval-identity-for-legendre-transform Analogy of Parseval identity for Legendre Transform ? Suresh Venkat 2011-02-02T23:17:34Z 2011-02-03T11:32:47Z <p>Parseval's identity states that the sum of squares of coefficients of the Fourier transform of a function equals the integral of the square of the function, or</p> <p>$$\sum_{-\infty}^{\infty} |c_n|^2 = (1/2\pi)\int^\pi_{-\pi} |f(x)|^2 dx$$ where the $c_i$ are the Fourier coefficients. </p> <p>The Legendre-Fenchel transform can be viewed as a generalization of the Fourier transform. For a given function $f : X \rightarrow R$ over a vector space $X$ which has dual <code>$X^{*}$</code>, the transform $f^* : X^* \rightarrow R$ is defined as: $$f^*(p) = \sup_{x \in X}\ \langle x, p\rangle - f(x)$$ where further $p = f'(x)$ is denoted as <code>$x^*$</code>. So my question is: Is there any natural generalization of Parseval's identity to relate $f^*$ and $f$ ? To be specific, I'm trying to relate quantities like $\|x-y\|$ to $\|p - q\|$ where <code>$p = x^*, q = y^*$</code></p> http://mathoverflow.net/questions/49989/algorithm-for-k-medians-in-a-convex-polygon/50146#50146 Answer by Suresh Venkat for Algorithm for k-medians in a convex polygon Suresh Venkat 2010-12-22T10:11:57Z 2010-12-22T10:11:57Z <p>The problem you're asking about (for $k=1$) is called the continuous Fermat-Weber problem. The primary work on this that I'm aware of is the <a href="http://arxiv.org/abs/cs/0310027" rel="nofollow">2003 paper by Fekete, Mitchell and Beurer</a>. While they examine this problem, they focus on the $\ell_1$ plane (the analytics are easier) and also pay more attention to the $k=1$ case, while also discussing some hardness results. </p> <p>My $.02$ is that there should be some way of getting an approximation by discretizing the region - it's not clear to me that convexity helps a lot though. </p> http://mathoverflow.net/questions/49226/classes-of-graphs-for-which-isospectrum-implies-isomorphism Classes of graphs for which isospectrum implies isomorphism ? Suresh Venkat 2010-12-13T08:31:35Z 2010-12-13T17:42:51Z <p>The spectrum of a graph is the (multi)set of eigenvalues of its adjacency matrix (or Laplacian, depending on what you're interested in). In general, two non-isomorphic graphs might have the same spectrum. </p> <p>Prompted in part by <a href="http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem" rel="nofollow">this discussion on reverse engineering a graph from its spectrum</a>, I was wondering: </p> <blockquote> <p>Are there interesting classes of graphs for which isospectrality implies isomorphism ?</p> </blockquote> http://mathoverflow.net/questions/49219/idiosyncratic-characterizations-of-ellp-for-p-not1-2-infty/49230#49230 Answer by Suresh Venkat for Idiosyncratic characterizations of $\ell^p$, for $p\not=1,2,\infty$ Suresh Venkat 2010-12-13T09:00:03Z 2010-12-13T11:48:05Z <p>$p$-stability singles out $0 &lt; p \le 2$. Specifically, there is no probability distribution $P$ such that the linear combination $\sum^n a_i X_i$ is distributed as $\|a\|_p Y$, where $X_1 ... X_n$ and $Y$ are random variables distributed according to $P$, if $p$ is not in the range $(0, 2]$. </p> <p>For $p = 0.5, 1, 2$ these distributions have closed-form expressions. </p> <p>(note: updated to reflect Gideon Schectman's comment)</p> http://mathoverflow.net/questions/48197/the-girthwidth-of-a-graph The "girthwidth" of a graph Suresh Venkat 2010-12-03T17:29:02Z 2010-12-06T07:43:47Z <p>Abstractly, tree/path decompositions of a graph $G$ can be thought of as doing the following:</p> <ul> <li>fix a "skeleton" class of graphs (tree or path)</li> <li>Pick a member of this class $H$. Associate with each node of $H$ a subset of vertices of $G$ such that (1) For each edge $e = (u,v)$ in $G$, there exists a node of $H$ containing both $u$ and $v$ and (2) the set of nodes of $H$ containing a fixed vertex of $G$ form a connected subgraph</li> <li>minimize the maximum cardinality of the set associated with a node of $H$, over all such associations and skeletons. </li> </ul> <p>Suppose that rather than choosing a tree or a path, we are allowed to pick any graph of girth at least $g$, for some fixed parameter $g$. Is there anything known about the resulting "girthwidth" of a graph ? </p> http://mathoverflow.net/questions/45849/optimal-binary-code-for-points-in-a-metricprobability-space/46332#46332 Answer by Suresh Venkat for Optimal binary code for points in a metric+probability space Suresh Venkat 2010-11-17T06:09:33Z 2010-11-17T06:09:33Z <p>The problem you're trying to solve is a generalization of what is called the '<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9437" rel="nofollow">continuous $k$-median problem</a>'. In that problem, the center locations are arbitrary, whereas in your case, they are on a grid. However, your problem starts with an arbitrary metric space. While the cited problem is NP-hard, and is likely to remain so for your problem, there are useful heuristics that you can try for the case when $X = {\mathbb R}^n$, including $k$-means-style methods. </p> <p>For example, you could fix a collection of centers on the grid, compute the Voronoi diagram, integrate your density within each cell to find the "average" location, and then "snap" this location to the nearest grid cell and repeat. </p> http://mathoverflow.net/questions/45211/planar-layouts-of-bipartite-graphs Planar layouts of bipartite graphs Suresh Venkat 2010-11-07T21:05:01Z 2010-11-07T22:47:11Z <p>Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar. </p> <p>It would be very convenient if there was a planar layout that had all the variable vertices in one line and all the clause vertices in a straight line. This can't be done because such a graph would be outerplanar, and $K_{2,3}$ isn't. </p> <p>But maybe a weaker layout is possible. </p> <blockquote> <p>Is it possible to lay out any planar bipartite graph $G = (A \cup B, E)$ such that</p> <ul> <li>All vertices of $B$ are on a straight line</li> <li>A can be partitioned into $A_1 \cup A_2$ such that all vertices of $A_1$ are on a parallel straight line to the left of $B$, and all vertices of $A_2$ are on a parellel straight line to the right of $B$.</li> </ul> </blockquote> <p>This seems to relate to <a href="http://mashfiquirabbi.110mb.com/files/thesis.pdf" rel="nofollow">track drawings of planar graphs</a>. </p> http://mathoverflow.net/questions/44902/relationship-between-these-two-probability-mass-functions/44904#44904 Answer by Suresh Venkat for Relationship between these two probability mass functions. Suresh Venkat 2010-11-05T00:52:23Z 2010-11-05T00:52:23Z <p>I'm not sure how interesting this is, but in the first case, straight multiplication yields that $E[X] = \lambda$, and $E[Y] = E[X^2]/\lambda$, which allows you to bound the second moment of $X$ in terms of $E[Y]$. </p> http://mathoverflow.net/questions/42207/maximum-average-value-within-a-rectangular-bounding-box/42256#42256 Answer by Suresh Venkat for Maximum average value within a rectangular bounding box Suresh Venkat 2010-10-15T05:54:31Z 2010-10-15T05:54:31Z <p>While your question <strong>as stated</strong> seems ill-formed (as commenters point out, the optimal solution is a 1x1 box around the maximum value), let's assume that there's some other constraint (MxN is too large for example, or there's a lower bound on the size of the query box) that makes this approach infeasible.</p> <p>In that case, at least for approximations, and if MxN is very large, an approach based on $\epsilon$-approximations might work for you. Roughly speaking, you're trying to do range querying over a set of ranges that are "well structured" (formally, have low VC-dimension) and you'd like to extract a sample of the input so that range queries on this sample approximate range queries on the real input. It turns out that a random sample of the input of size roughly $O(1/\epsilon^2 \log 1/\epsilon)$ would suffice to estimate the ranges within error $\epsilon$. Algorithmically, then you merely implement your expensive procedure on this small sample, and presumably that would be more efficient. </p> http://mathoverflow.net/questions/42192/preferred-embedding-of-finite-metric-spaces-in-riemaniann-manifolds-of-given-dime/42203#42203 Answer by Suresh Venkat for Preferred embedding of finite metric spaces in riemaniann manifolds of given dimension Suresh Venkat 2010-10-14T20:14:20Z 2010-10-14T20:14:20Z <p>This is almost certainly not what you want, but it illustrates why you need a tighter specification of 'preferred'. </p> <blockquote> <p>Any $n$-point metric space can be embedded isometrically in $\ell_\infty^n$.</p> </blockquote> <p><strong>Proof</strong>: (this is a well known result): Let the $r^{th}$ coordinate of $x_j$ be the distance from $x_i$ to $x_r$. BY triangle inequality, we know that for any triple $i,j,k$, $$d(x_i,x_j) - d(x_k, x_j) \le d(x_i, x_k)$$ which establishes the correctness of the embedding. </p> <p>One interesting notion of preferred therefore might be that the target space dimension is either independent of $n$, or at the very least depends sublinearly on $n$. </p> http://mathoverflow.net/questions/41838/higher-order-dimension-in-posets-a-reference-request Higher-order dimension in posets: a reference request Suresh Venkat 2010-10-11T22:38:30Z 2010-10-11T22:38:30Z <p>Let $P = (X, \le)$ be a partially-ordered set. Then the dimension of $P$ is the minimum number of total orders over $X$ whose intersection yields $P$. Alternately, the dimension of $P$ is the minimum dimension of an isomorphic embedding of $P$ into $R^d$ endowed with the dominance partial order: $(x_1, \ldots x_d) \preceq (y_1, \ldots, y_d)$ if for all $i$, $x_i \le y_i$. </p> <p>The set of total orders (the <em>realizers</em>) that witness the dimension can be thought of as witnessing all possible legal <em>pairwise</em> orderings in any linear extension of $P$: if $a, b$ are not comparable in $P$, then both $a\le b$ and $a \ge b$ must be witnessed by realizers. </p> <p>There is a higher-order generalization of the dimension, defined as follows. Fix a parameter $r &lt; |X|$. Then the $r$-dimension of $P$ is the minimum number of total orders that witness all legal ordering relationships among $r+1$-tuples of elements in $P$. </p> <p>For example, the trivial poset $\{a,b,c\}$ (no orderings) has dimension two via the two orderings $a,b,c$ and $c,b,a$. However, this poset has a 2-dimension of 6, because we need all the $3!=6$ orderings of the three elements. </p> <blockquote> <p>Question:</p> <ol> <li>Is there any known geometric interpretation of the $r$-dimension like what we have for the dimension ? </li> <li>Are there known bounds on the $r$-dimension ? For example, we know that the dimension is upper bounded by the width (and this is a fairly weak bound in general).</li> </ol> </blockquote> http://mathoverflow.net/questions/27058/vector-valued-valuations-on-lattices Vector-valued valuations on lattices Suresh Venkat 2010-06-04T15:56:13Z 2010-10-10T06:06:18Z <p>There's a fair amount of work on valuations on (modular) lattices, by which I mean functions $v : \mathcal{L} \rightarrow R$ that satisfy the modular expression $$v(x) + v(y) = v(x \wedge y) + v(x \vee y)$$</p> <p>I'm wondering if there's been any work on vector-valued valuations (where the range of v is $R^k$ and the same relation holds) ? </p> <p>In addition, I'm also interested in lower valuations (I'm not sure if this name is standard) that satisfy the submodular inequality $$v(x) + v(y) \ge v(x \wedge y) + v(x \vee y)$$ and possibly the generalization to $R^k$ where we replace the above by $$v(x) + v(y) \succeq v(x \wedge y) + v(x \vee y)$$ ($\succeq$ being the coordinate-wise partial order)</p> <p>This is a reference request, for the most part. </p> http://mathoverflow.net/questions/15964/constructing-a-metric-over-a-lattice Constructing a metric over a lattice Suresh Venkat 2010-02-21T06:45:47Z 2010-10-10T06:04:36Z <p>Consider a lattice $({\cal L}, \wedge, \vee)$ with an antimonotonic function $f: {\cal L} \rightarrow {\mathbb R}$ defined on it (i.e $x \preceq y \implies f(x) \ge f(y)$). </p> <p>$f$ is said to be submodular if for all $x,y \in {\cal L}$, $$f(x) + f(y) \ge f(x \wedge y) + f(x \vee y)$$ and supermodular if the inequality is flipped (again for all $x,y$). </p> <p>It's generally known (there's an easy proof), that a submodular $f$ induces a metric on ${\cal L}$ via the defn $$d_s(x,y) = 2f(x \wedge y) - f(x) - f(y)$$. If $f$ is supermodular, then the construction $$d^s(x,y) = f(x) + f(y) - 2f(x \vee y)$$ yields a metric. </p> <p><strong>Question</strong> I'm dealing with an $f$ that is nether sub- nor supermodular. I can define the "distance" $$d(x,y) = \min ( d^s(x,y), d_s(x,y))$$</p> <p><strong>Conjecture</strong>: $d(x,y)$ is a metric. </p> <p>I have very little sound mathematical intuition for why this conjecture should be true, and bucketloads of empirical evidence (from a lattice I'm actually working with). This seems like the kind of thing that if true, would be reasonably well known to experts, and if false, might have a clear counterexample. So this is a plea for help. </p> <p>Since it might make a difference, I should mention that the lattice I'm working with is nondistributive in general, but it has distributive sublattices where I'm still unable to prove the conjecture. </p> http://mathoverflow.net/questions/41362/analyzing-weighted-set-cover-variant/41367#41367 Answer by Suresh Venkat for Analyzing Weighted Set-Cover variant Suresh Venkat 2010-10-07T05:07:59Z 2010-10-07T05:07:59Z <p>Rather than focusing on the greedy algorithm, you could also look at the LP formulation. Let's take the specific cost function that you provide. Notice that each element of A is charged $k_1$ if it appears at all in the cover, and each element of $D$ is charged $-k_2$ if it appears in the cover. </p> <p>Given that, and the fact that you have to cover all elements in $D$, it means that you're going to incur a fixed cost of $-k_2 |D|$ regardless of what else you do, so you might as well ignore it for the purpose of finding the solution. </p> <p>This leaves the elements in $A$. Set up an LP where there's an indicator variable $x_S$ for each set $S$ as usual, and a variable $y_a$ for each element $a \in A$. Now your cost function can be written as $$C = k_1\sum y_a - \sum |S| x_S$$ subject to the constraints $$\forall S, 0 \le x_S \le 1$$ $$\forall a, S \text{ contains } a, x_S \le y_a$$ Notice that the second constraint ensures that you have to charge a cost to $y_a$ if you pick any of the sets that contain it. The minimization of $C$ ensures that you'll always pick $y_a = x_S$ for some $S$. </p> <p>At this point you have either an LP-rounding problem to solve (and you can look at standard ways of solving set-cover-ish LPs via rounding), or you can think of the primal-dual formulation, which essentially leads to greedy in any case. </p> http://mathoverflow.net/questions/38855/nodes-clusters-with-a-distance-matrix/38928#38928 Answer by Suresh Venkat for Nodes clusters with a distance matrix Suresh Venkat 2010-09-16T05:26:22Z 2010-09-16T05:26:22Z <p>Where do the distances in $M$ come from ? this is somewhat important. for example, is it guaranteed that $M$ is a metric (i.e satisfies triangle inequality) ? Further, are the distances simple Euclidean distances ? As an aside, how can you even run $k$-means ? $k$-means requires a vector space, so that centroids are well defined. In your example, you appear to be considering a discrete distance space.</p> <p>While $k$-means and spectral clustering (which is really spectral dimensionality reduction followed by $k$-means) are fine algorithms, possibly a more important question to ask is: what kind of measure do you want to optimize ? $k$-means tries to (but doesn't) minimize the sum of squared distances between points in a cluster and their centroid. </p> <p>In your example, you could ask for the $k$-clustering that minimizes the maximum radius of a cluster, where the radius is defined as $r = \min_{p \in C} \max_{q \in C} d(p,q)$. This is easy to approximate within a factor of 2 by picking $k$ maximally separated points. </p> http://mathoverflow.net/questions/38245/what-is-the-easiest-randomized-algorithm-to-motivate-to-the-layperson/38270#38270 Answer by Suresh Venkat for What is the easiest randomized algorithm to motivate to the layperson? Suresh Venkat 2010-09-10T05:30:14Z 2010-09-10T05:30:14Z <p>While this requires the use of approximation as well as randomization, I always find the idea that you can get a good estimate of a population by sampling a constant sized set to be very non-intuitive and powerful. The way I usually phrase it in class is: you want to poll the population so that any reasonably popular group is represented. If "reasonably" popular" is defined as a constant fraction, then you only need to sample a <strong>constant number of people</strong> to hit all groups. Judging by how the general population gets confused by polls, this seems like a good example. </p> <p>Another example that's more useful for a "CS-aware" layperson is one that requires knowledge of the notion of a median. You can get a quick and dirty approximation for the median in <strong>constant</strong> time by sampling (in fact, the median of THREE random elements suffices), and the more you sample, the better the approximation. </p> <p>Probably the most spectacular demonstration of the power of randomness, but one alas that isn't easy to prove to a layman, <a href="http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf" rel="nofollow">is the power of two choices</a>. It seems almost impossible that it's true, but it is. </p> http://mathoverflow.net/questions/37211/permutations-with-identical-objects/37218#37218 Answer by Suresh Venkat for Permutations with identical objects Suresh Venkat 2010-08-31T05:37:26Z 2010-08-31T05:37:26Z <p>Here's a sketch of an idea. Consider first the problem of computing the number of permutations of $k$ elements <em>given</em> the number of elements $n_i$ in each class. This is easy: it works out to $$\frac{k!}{\Pi_i n_i !}$$ because in any fixed string, you can permute the elements in a class without changing the string. </p> <p>Now consider the problem of writing down the different partitions of $k$ into the sum of $x$ <em>labelled</em> numbers. Merely finding the sum itself can be done by determining the coefficient of $y^k$ in the polynomial $$\Pi_i \frac{y^{r_i+1}-1}{y-1}$$</p> <p>But this is not enough, since you need to weight each such partition by a different number. However, we know that the contribution of $y^i$ must be $1/i!$, so the overall number we are looking for is $k!$ times the coefficient of $y^k$ in the polynomial $$\Pi_i \sum_{j=0}^{r_i} \frac{y^j}{j!}$$</p> http://mathoverflow.net/questions/11562/suggest-effective-heuristic-not-precise-graph-colouring-algorithm/36521#36521 Answer by Suresh Venkat for Suggest effective heuristic (not precise) graph colouring algorithm Suresh Venkat 2010-08-24T05:25:12Z 2010-08-24T05:25:12Z <p>There are a number of heuristics that work fairly well. They all work by prescribing some kind of ordering on the vertices, and then coloring the vertices one by one, using the least unused color to color the next one. </p> <ul> <li>First Fit does precisely the above, with an arbitrary initial ordering. It's fast, but needless to say performs rather poorly.</li> <li>LDO orders the vertices in decreasing order of degree, the idea being that the large degree vertices can be colored more easily. </li> <li>SDO (saturation degree ordering) is a variant on LDO where the vertices are ordered in decreasing order by "saturation degree", defined as the number of distinct colors in the vertex neighborhood. </li> <li>IDO (incidence degree ordering) is a variant of SDO where the "degree" of a vertex is defined as the number of colored vertices in its neighborhood. </li> </ul> <p>The latter two heuristics require the order to be rebuilt after each step, and so are more expensive, but there's <a href="http://www.cs.purdue.edu/homes/agebreme/publications/PhDThesis.pdf" rel="nofollow">empirical evidence</a> suggesting that they do reasonably well, especially in parallel. </p> <p>None of these algorithms come with any kind of formal guarantees, so be warned. </p> http://mathoverflow.net/questions/36420/is-the-solution-bounded-diophantine-problem-np-complete/36422#36422 Answer by Suresh Venkat for Is the solution bounded Diophantine problem NP-complete? Suresh Venkat 2010-08-23T02:21:33Z 2010-08-23T02:21:33Z <p>Seems to me that you could encode SAT in the usual polynomial manner, with variables restricted to being 0 or 1. </p> http://mathoverflow.net/questions/36035/what-is-the-most-general-class-of-metric-spaces-for-which-the-closest-pair-of-poi/36166#36166 Answer by Suresh Venkat for What is the most general class of metric spaces for which the closest pair of points in a finite subset can be found in time O(n^(1+eps))? Suresh Venkat 2010-08-20T03:29:31Z 2010-08-20T03:29:31Z <p>Another approach you can take is as follows. Since the closest pair can be solved by $n$ invocations of a nearest neighbor query, you could examine the set of techniques available for performing near-neighbor queries in $n^\epsilon$ time. </p> <p>In this regard, <a href="http://www.almaden.ibm.com/u/kclarkson/nn_survey/p.pdf" rel="nofollow">Ken Clarkson's survey of nearest neighbor methods in metric spaces</a> is quite helpful. Among the things he does is review various properties of metric spaces and how they influence the running time of NN algorithms (the doubling dimension mentioned by David is one example considered here). </p> http://mathoverflow.net/questions/36105/nonasymptotic-complexity-results/36161#36161 Answer by Suresh Venkat for nonasymptotic complexity results Suresh Venkat 2010-08-20T02:47:55Z 2010-08-20T02:47:55Z <p>Are you by any chance referring to examples like Haken's proof that the pigeonhole principle requires exponentially long resolution proofs ? </p> http://mathoverflow.net/questions/35664/why-relativization-cant-solve-np-p/35678#35678 Answer by Suresh Venkat for Why relativization can't solve NP !=P? Suresh Venkat 2010-08-15T18:11:29Z 2010-08-15T18:11:29Z <p>I was holding off on posting a non-answer, but am encouraged by JDH. </p> <p>There's still something deeply puzzling about the idea that if $A = B$, there's possibly an oracle for which $A^O \ne B^O$, and that seems to be at the heart of the OP question. In that respect, ilyaraj's example of IP and PSPACE is actually better, because unlike with P and NP, where we don't know the true answer, we actually KNOW that IP = PSPACE, and yet there's still an oracle that separates them.</p> <p>But I think a deeper explanation needs to go beyond relativization, to the properties that relativization relies on. <a href="http://www.cs.princeton.edu/theory/complexity/diagchap.pdf" rel="nofollow">The Arora-Barak book explains this quite well</a>: they point out that proofs like diagonalization rely on efficient simulation (universality) and the ability to list out machines (enumeration), and that any oracle-based result relies ONLY on these two properties. </p> <p>Thus, the real answer to why P vs NP is independent of relativized arguments is that you need to exploit more information than just universality and enumeration. This comes to mind precisely because of the "new" barrier coming out the Deolalikar proof discussions, that proof techniques that try to differentiate the geometry of solutions to SAT vs P-time problems can't work. </p> http://mathoverflow.net/questions/35422/most-obvious-open-problems-in-complexity-theory/35550#35550 Answer by Suresh Venkat for Most 'obvious' open problems in complexity theory Suresh Venkat 2010-08-14T00:32:35Z 2010-08-14T00:32:35Z <p>GI $\in$ P. We know that there are <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem#cite_note-3" rel="nofollow">bad consequences</a> if GI is NP-complete, </p> <p>p.s GI is graph isomorphism</p> http://mathoverflow.net/questions/112626/2-coloring-a-planar-hypergraph/112642#112642 Comment by Suresh Venkat Suresh Venkat 2012-11-18T05:43:44Z 2012-11-18T05:43:44Z I see. the problem is that a rank three hypergraph will have edges of size 2 as well (in fact these are used in the NP-completeness for general hypergraphs) http://mathoverflow.net/questions/112626/2-coloring-a-planar-hypergraph Comment by Suresh Venkat Suresh Venkat 2012-11-18T05:42:10Z 2012-11-18T05:42:10Z It's not about coloring planar graphs per se (see Brendan McKay's answer) http://mathoverflow.net/questions/106878/non-probabilistic-proof-of-the-johnsonlindenstrauss-lemma Comment by Suresh Venkat Suresh Venkat 2012-09-11T05:46:55Z 2012-09-11T05:46:55Z For example, this paper: <a href="http://arxiv.org/abs/1006.3585" rel="nofollow">arxiv.org/abs/1006.3585</a> that constructs the associated matrices using bounded independence hash functions. http://mathoverflow.net/questions/106878/non-probabilistic-proof-of-the-johnsonlindenstrauss-lemma Comment by Suresh Venkat Suresh Venkat 2012-09-11T05:45:48Z 2012-09-11T05:45:48Z There are derandomized constructions of the matrices involved in the JL projection, if that's something that interests you. http://mathoverflow.net/questions/106356/distance-calculation-in-metric-space Comment by Suresh Venkat Suresh Venkat 2012-09-06T07:09:37Z 2012-09-06T07:09:37Z If you're in a low dimensional space, then your problem reduces to performing a set of point location queries in a farthest-point Voronoi diagram under the appropriate metric. http://mathoverflow.net/questions/106356/distance-calculation-in-metric-space/106377#106377 Comment by Suresh Venkat Suresh Venkat 2012-09-06T07:07:32Z 2012-09-06T07:07:32Z This is not quite facility location because you're not &quot;searching&quot; for facilities in the OP's question - you're given the facilities (the set A) http://mathoverflow.net/questions/43690/whats-a-mathematician-to-do/44213#44213 Comment by Suresh Venkat Suresh Venkat 2012-08-22T22:39:16Z 2012-08-22T22:39:16Z This seems like an ideal counterpoint to Hardy's Lament. I'm calling it Thurston's Paean :). Seems poignant now that he has passed. http://mathoverflow.net/questions/92620/known-graph-surface-invariants-that-can-be-extracted-from-homology-over-different/92626#92626 Comment by Suresh Venkat Suresh Venkat 2012-03-30T02:10:50Z 2012-03-30T02:10:50Z So you're saying that they are all equivalent ? http://mathoverflow.net/questions/83871/fuzzy-vector-similarity/83883#83883 Comment by Suresh Venkat Suresh Venkat 2011-12-22T05:40:06Z 2011-12-22T05:40:06Z Note that this construction is almoot identical to the construction that induces the Mahalanobis distance between two vectors, when M is positive definite. http://mathoverflow.net/questions/18217/travelling-salesman-problem/82850#82850 Comment by Suresh Venkat Suresh Venkat 2011-12-07T05:52:27Z 2011-12-07T05:52:27Z But the hamming distance satisfies the triangle inequality. http://mathoverflow.net/questions/79419/exponential-or-other-families-of-distributions-on-manifolds/79424#79424 Comment by Suresh Venkat Suresh Venkat 2011-10-29T20:58:57Z 2011-10-29T20:58:57Z Thanks. I'll check out both these references. The first one in particular has some elements that seem useful. http://mathoverflow.net/questions/79419/exponential-or-other-families-of-distributions-on-manifolds Comment by Suresh Venkat Suresh Venkat 2011-10-29T20:57:26Z 2011-10-29T20:57:26Z @Suvrit that is correct. You can get one kind of normal distribution equivalent using the heat kernel. http://mathoverflow.net/questions/79419/exponential-or-other-families-of-distributions-on-manifolds Comment by Suresh Venkat Suresh Venkat 2011-10-28T22:03:00Z 2011-10-28T22:03:00Z Hi Joe, I'm specifically looking for random vars whose values are points on a manifold. @Deane, information geometry (which I'm familiar with) deals with how to represent families of distributions as manifolds (or submanifolds), which is different to building a probability distribution ON a manifold. http://mathoverflow.net/questions/79419/exponential-or-other-families-of-distributions-on-manifolds Comment by Suresh Venkat Suresh Venkat 2011-10-28T18:24:43Z 2011-10-28T18:24:43Z I guess my question isn't so much &quot;can it be done&quot; as much as &quot;has it been done for any specific settings and what references do I need to look at&quot;. In particular, in the context of statistical estimation . http://mathoverflow.net/questions/74759/survey-on-structural-complexity Comment by Suresh Venkat Suresh Venkat 2011-09-12T07:33:25Z 2011-09-12T07:33:25Z A book that needs to be updated, but was perfect at the time, was Structural Complexity by Balcazar, Diaz and Gabarro: <a href="http://books.google.com/books/about/Structural_complexity.html?id=GRfvAAAAMAAJ" rel="nofollow">books.google.com/books/about/&hellip;</a>