1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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., ...
4
votes
0answers
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$ ...
-3
votes
1answer
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 ...
5
votes
1answer
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 ...
7
votes
0answers
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 ...
-2
votes
0answers
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 ...
-6
votes
0answers
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 ...
-4
votes
0answers
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 - ...
1
vote
1answer
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$, ...
7
votes
0answers
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 ...
-1
votes
0answers
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, ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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?
-1
votes
0answers
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 ...
-1
votes
0answers
37 views

The algorithm yields optimal ternary codes [on hold]

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree. Create a leaf node for each unique character and build a min ...
-1
votes
1answer
49 views

convertion into integer linear program for Ising spin state problem [on hold]

I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem) $$ maximise: ...
-2
votes
0answers
52 views

Confusion Regarding the Formal Definition of P/Poly and SAT-Languages [on hold]

My understanding of the Circuits and Circuit family of Size(F(n)) is as follows: A Circuit family of Size(F(n)) is a set of circuits, the ith Circuit has i input Lines and 1 Output Line, with the ...
-3
votes
0answers
48 views

number of edges and weights in shortest paths?

We know the bellman-ford algorithms check all edges in each step, and for each edge if, d(v)>d(u)+w(u,v) then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the ...
-4
votes
0answers
38 views

What happens when google's url shortener runs out of urls? [on hold]

Google allows you to generate shorter links that will redirect users to the proper page. The generated url is 6 characters long, and has lower, upper, and numeric characters. This allows ...
-2
votes
1answer
24 views

arbitrary segment stabbing query for 2d segments

Store a set of 2d segments S in some data structure. For an arbitrary query 2d segment q, answer a yes/no question in sublinear time: whether q intersect with any segment in S? If the query is a ...
0
votes
0answers
96 views

Evaluating the expected value of negatively correlated random variables

A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, ...
4
votes
1answer
150 views

Sample complexity of distinguishing two Gaussian distributions?

Below is a description of the problem: Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$. And I can get $n$ samples ...
-6
votes
0answers
23 views

Proof for Max flow for a single path = Min of all cuts of Max edge capacity in a single cut [on hold]

Let G=(V,E) be an undirected graph with capacities $c_e$ on each edge e $\in$ E. Let s,t be two of its vertices. Let ${\bf P}$ be the set of s-t paths in G and ${\bf C}$ be the subsets of edges that ...
1
vote
1answer
114 views

What is a “level-r pseudo expectation functional”?

In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction ...
0
votes
0answers
65 views

CSP-problem, based on context-free grammar

I'm trying to solve a CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production ...
-1
votes
0answers
27 views

Any easy step-by-step explanations of the Universal Approximation Theoreom? [closed]

I am writing a math report as part of my final year project and one of the chapters discusses the Universal Approximation Theorem. I tried reading Cybenko's and Hornik's relevant papers since they ...
6
votes
1answer
133 views

Why it's impossible to declare an induction principle for Church numerals

Imagine, we defined natural numbers in dependently typed lambda calculus as Church numerals. They might be defined in the following way: ...
2
votes
1answer
102 views

Deciding satisfiability and non-validity

For propositional logic, a decision procedure for satisfiability can be turned into a decision procedure for non-validity by giving it the negated version of a formula. Does this hold for all logics ...
3
votes
1answer
100 views

Rate of convergence for the Perron–Frobenius theorem

The Perron–Frobenius Theorem states the following. Let $A = (a_{ij})$ be an $n \times n$ irreducible, non-negative matrix ($a_{ij} \geq 0, \forall i,j: 1\leq i,j \leq n$). Then the following ...
0
votes
0answers
48 views

Encoding the natural numbers modulo n successor relation in SAT [closed]

Let's say we have a number of propositional symbols $b_0,\ldots,b_{n-1}$, used to represent an $n$-bits binary number. How is it possible to encode the successor relation of the integers modulo $2^n$ ...
2
votes
0answers
38 views

How to simulate sequential registers from causal ones?

Background: In distributed shared memory (DSM) model, the problem of register simulations/constructions is to simulate registers with certain characteristic out of registers with weaker features. For ...
6
votes
0answers
53 views

Learning read-once branching programs with membership queries

Let $B=\{0,1\}$. A read-once branching program of width $n$ and size $w$ is given by a graph with layers $0,\ldots, n$, where the first layer has just the starting node, the last layer has nodes ...
0
votes
0answers
42 views

Implementation of Sparse Johnson Lindenstauss Lemma [on hold]

I am trying to implement the sparse Johnson Lindenstrauss in matlab from the paper: Sparser Johnson-Lindenstrauss Transforms by Daniel M. Kane and Jelani Nelson. Can somebody give pointers on how to ...
0
votes
0answers
45 views

What are good journals for publishing a paper? [duplicate]

I wish to publish my research work. But do not have a good idea about how and where to publish.
6
votes
1answer
90 views

Array implementation of dictionary data structure

Is there a data structure that supports searching, inserting, deletion in worst-case O(log n) time and that satisfies the following "array implementation" property: at any point in time, the data ...
2
votes
1answer
53 views

How to exploit knowledge of the sampling distribution for better generalization bounds?

In the PAC learning model, suppose the learner actually knows the sampling distribution $P$. Surely this knowledge can be exploited to yield better generalization bounds -- but how? One idea is using ...
5
votes
1answer
63 views

Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?

In Feldman-Gopalan-Khot-Ponnuswami 06 the authors show that agnostically learning parities reduces to learning parities with random classification noise. They also remark (among other things) that ...
6
votes
0answers
66 views

Why Tomita created GLR and didn't use Earley?

When I look at Earley parsing, it looks very elegant, and I wonder why GLR techniques become popular? Does anyone know what was wrong with Earley parsing that Tomita created GLR? Performance? Any ...
-2
votes
0answers
38 views

Relation between Kolmogorov complexity and Compression function

The Kolmogorov complexity of string x is defined as length of the shortest program that generate the string x. Suppose the string x is n bits. Now there are 2^n strings of length n and by the ...
-3
votes
0answers
32 views

page table question in c [closed]

I got a question with page table. The page table was stored in a set of dedicated CPU registers, with one register storing the location of each page. Why isn’t this common on modern computer systems?
-1
votes
0answers
61 views

Examples of algorithms which build graphs via perfect matchings [closed]

Are there examples of algorithms which try to build a graph (say a bipartite graph) by adding the edges in order of perfect matchings? Any proof technique known which can exploit this structure that ...
6
votes
3answers
160 views

Ramification of An Impredicative Type Theory

Most type theories that I'm aware of are predicative by which I mean that Void : Prop Void = (x : Prop) -> x isn't well-typed in most theorem provers as this ...
8
votes
2answers
222 views

Implications of a problem being in XP when parameterized by diameter

Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if ...
-5
votes
0answers
30 views

two phase commit protocol [closed]

In the 2PC protocol the coordinatorfirst decides Commit (by writing a commit record to its site’s DT log) and then sends COMMIT messages to the participants. Suppose the order of these two steps is ...
10
votes
2answers
442 views

Fun with inverse Ackermann

The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann. $$\alpha_1(n) = [n/2]$$ $$\alpha_2(n) = ...

15 30 50 per page