All Questions

23 views

Communication complexity of Independent Set game?

Consider the following communication game. Independent Set game Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$. Alice receives a set $X$ of edges, each ...
8 views

Applications of network clustering coefficient

Consider the global clustering coefficient of a graph as defined here . The clustering coefficient describes how likely it is for a random connected triplet of vertices to be closed. My question ...
58 views

What are multiple rounds of SOS/Lasserre hierarchy?

Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things? Or to take a ...
10 views

What does the term ' complete-state formulation ' mean?

I read the term being used to describe a local-search (hill-climbing) algorithm in Machine translation. Quoting relevant text below: The strategy of ReWrite, as described in (Ger- mann et al., ...
46 views

Applications of small Kakeya sets over finite fields

It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$. For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...
34 views

Complicated Huffman coding [on hold]

I am trying to figure out how to code these symbols. I am pretty sure I have it, but it gets a little tricky. Let A,B, and C have probabilities .71, .16, and .13 respectively. I am trying to code the ...
93 views

Numerical precision in sum-of-squares method?

I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the ...
65 views

s-t connectivity on infinite planar graphs with finite description

I would like to know if the following problem is known and has been studied: Consider an infinite directed graph that can be built on the infinite lattice "tiling" a finite set of subgraphs, more ...
33 views

A interest but odd bipartite matching or assignment problem KM cannot solve

Currently, I try to solve a strange problem in my study. Consider a weighted bipartite graph n*m, n represents the number of user who generate task, and m represents the number of "solver" who can ...
32 views

how to write this java programming [on hold]

Enter all the names into the array Sort the names according to the order selected by the user (ascending or descending) Display the names with a list number before each name (i.e. 1. Ali Wong) Copy ...
14 views

Interactive 3D Graphics course review? [on hold]

Interactive 3d graphics course - https://www.udacity.com/wiki/cs291/syllabus has all the information which is in Real time rendering book - ...
112 views

The Goemans-Williamson algorithm in the $SOS$ framework

If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...
127 views

Are there sparsifiers that approximate vertices rather than edges?

Originally introduced by Benczur and Karger, cut sparsifiers let one take a dense graph $G=(V,E)$ and produce a weighted sparse graph on the same vertex set, where - only knowing the sparse graph ...
32 views

Proving NP-hardness of scheduling problem (total weighted completion time)

Consider the problem $P \mid \mid \sum w_j C_j$. I want to prove that this problem is (strongly) NP-hard by reducing from $3$-Partition, but I am not really sure how to do this. Just to be precise, ...
45 views

Conditions for being non-co-spectral

A regular graph(= a symmetric matrix) G has a set of eigen values . $u, v \in G$, has no adjacency. if, in the matrix of G, adjacency of u, v is created(the entry of index (u,v) will be 1 from ...
42 views

Bounding Rademacher Averages, with and without chaining

One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma: $$R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n}$$ where ...
54 views

Problems needs solutions in Distributed computing?

This is same as question. The answer for the question is 3 years old. Since the old topics will be quickly outdated or solved and new research problems arises, it would be great to know the latest ...
24 views

Dynamically maintaining heavy light decomposition

How could one maintain a heavy light decomposition of a forest of trees, while adding or removing edges?
44 views

Obfuscating models of pure computation

Similar question: Is anyone actively researching distributed prediction models? Imagine there's a network of computers containing and exchanging multiple models of pure computation. The network is ...