0
votes
0answers
6 views

How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant?

Given a random graph on $n$ vertices where each edge is included with probability $1/2$. Lets call it $G=(n,1/2)$. How can we show that the probability that this graph has a stable set of size at ...
-2
votes
0answers
21 views

Use of jackson structured program

Here is a question related to jackson structured program. I am very new to this concept. Can you please help me out by providing a solution to this question here. Q: ABC Company requires a tool to be ...
3
votes
0answers
38 views

Are there works on function complexity classes not included in FNP?

Are there book chapters on classes of function problems not contained in FNP? If not, are there research articles on this topic?
2
votes
0answers
25 views

Average number of sets given by greedy set cover? Is it uniform distribution?

We're covering the whole random universe $U$ of size $m$ with random sets $S_{1},\dots S_{n}$. I know that greedy set cover gives us a number between size of the minimal set cover and size of the ...
0
votes
1answer
102 views

Information-theoretic Diffie-Hellman

The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand. In Diffie-Hellman Alice and Bob ...
3
votes
0answers
93 views

What is the application of combinatorial game theory

I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are ...
8
votes
0answers
85 views

Smallest possible universal combinator

I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal ...
3
votes
1answer
110 views

Assignment problem with multiple workers for each job

I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given ...
-2
votes
0answers
51 views

is every L in pspace-complete is nl hard? if yes then why? [on hold]

is every L in pspace-complete is nl hard? if yes then why? if not then why cant there be L that is pspace complete and in NL?
2
votes
0answers
67 views

What is the computational complexity of sin and cos for floating point inputs?

What is the computational complexity of the problem INPUT: $\;\;\;$ integers $x$ and $y \:$ (both in binary) OUTPUT: rational approximations to $\: \sin\hspace{-0.03 in}\left(x\hspace{-0.04 ...
1
vote
0answers
50 views

Is joint Kolmogorov Complexity order invariant?

Due to the symmetry of information, it follows up to an additive constant that K(X,Y) = K(Y,X) Does this hold for more than two data objects as well?
0
votes
1answer
69 views

What are some of the most ingenious linear programs developed for tackling hard combinatorial problems? [on hold]

I would like to know about some known ingenious linear programs that have been developed for tackling hard combinatorial optimization problems. Especially any linear programs which had helped in ...
3
votes
2answers
186 views

What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?

As title says what happens to other complexity classes if all $\#P$ (Sharp-P) problems have polynomial-time algorithms? What happens to PSPACE?
4
votes
1answer
88 views

Hierarchy theorem for NTIME intersect coNTIME?

$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap ...
-1
votes
0answers
19 views

References for family network studies

Is there any recent review/list of research articles/book on studies of family networks from the network science/theory point of view? I am studying network properties of family trees of a few ...
2
votes
1answer
81 views

Finding a random regular graph with degree d

I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$. For $d \in 2\mathbb{N} +1$ this trivially is impossible as no ...
-1
votes
0answers
31 views

Estimate the cut edges in graph partitionining

Consider a large graph consisting of n nodes and e edges and an average degree of 2*e/n that is partitioned in k subgraphs such that the partitions are balanced, i.e. equal number of nodes at each ...
-2
votes
1answer
78 views

Why are there only two bits? [on hold]

I was thinking that why are their only two bits,0&1. I know that they represent a particular switch in IC being opened or closed. But why not for switch neither completely open nor closed i.e. in ...
-2
votes
0answers
23 views

Difference in complexity in checking the acceptance of a word vs finding an accepting word [on hold]

We know that the complexity of checking whether some word $w$ is accepted by a turing machine $TM$ is undecidable. But what about the complexity of finding one accepting word of a $TM$? Are these two ...
0
votes
0answers
55 views

“Elements of Information Theory”: Some (basic) help needed here

I was following the textbook by Cover & Thomas (2006): Elements of Information Theory. (hyperlink is not owned by me) I have one question that has been irking for me some time. It is regarding ...
2
votes
0answers
134 views

Is the nonnegativeness of a polynomial hard for $\mathsf{NP}_\mathbb{R}$?

It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$. Input: a list $P$ of triplets $(a,s,t)$ where $s$ and $t$ are nonnegative integers. Output: is there an $x\in \mathbb{R}$ such ...
3
votes
0answers
78 views

NP-hardness of a quadratic programming problem

Motivated by the mean-variance optimization, I came up with the following question: Given $n$ integers $a_1, \cdots, a_n$; $n$ lower bounds $0<\ell_1, \cdots, \ell_n<1$ $n$ upper bounds ...
1
vote
1answer
61 views

Finding all possible simple cyclic paths in a digraph

I have a strongly connected component with over 200 vertices and more than 600 edges. I need to iterate through each simple cycle in the graph exhaustively, without specifying a particular node. Is ...
5
votes
1answer
167 views

Does this problem related to subset sum have a name?

I'm looking for research into this problem -- computational complexity, solution algorithms, approximation algorithms, etc. If it has a canonical name, that would help me look into prior research. ...
6
votes
1answer
87 views

Lexicographic perturbation for euclidean shortest path instances?

Assume we have an undirected graph $G=(V,E)$ and vertex locations $\pi: V \rightarrow \mathbb{R}^2$. I am looking for a procedure to perturb the vertex positions to obtain new positions $\pi'$ such ...
4
votes
0answers
72 views

Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs

Let $G=(V, E)$ be an undirected simple graph. Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space ...
8
votes
1answer
457 views

Problems with no quantum advantage

I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer. To start things off, I think computation of ...
3
votes
0answers
67 views

Complexity of eigenvaue problem

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices). What is the best time lower bound it is known? ...
-1
votes
0answers
88 views

If a problem is not in NP, does it have to be NP-hard [closed]

Is every non-NP problem NP-hard? In other words, does every problem in NP reduce (in polynomial time) to every problem outside of NP? Equivalently, does 3SAT (or your favorite other NP-complete ...
0
votes
1answer
32 views

Efficiently picking free position from array with uniform probability.

For each array position it is known if position filled or not. How efficiently pick one free position with uniform probability? That task happen during implementation of AI by Monter-Carlo method ...
1
vote
0answers
16 views

Minimum cost flow with Demand and Edge Capacity scaling

Consider a the splittable minimum cost flow problem on network $G(V,E,W,C)$ and a set of commodities $(s_i,t_i)$ with demand $d_i$ for $i=1,2,\dots,k$. Here, $w_e$ and $c_e$ is the weight of edge $e$ ...
8
votes
1answer
240 views

Does P/poly $\neq$ NP/poly have any interesting implications?

$P/poly = NP/poly$ implies $NP \subseteq P/poly$, which in turn has interesting consequences like the collapse of the polynomial hierarchy. Are there interesting implications for $P/poly \neq ...
2
votes
0answers
30 views

moments of complexity for random restriction

Suppose C is a large circuit computing a function $f:2^n \rightarrow 2^m$. For a function $g$ let $B(g)$ denote the size of the minimal Boolean circuit computing $g$. What can be said about the ...
16
votes
0answers
208 views

$\Delta = 57, d=2$ Moore Graph

I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years. You may recall that Hoffman and ...
11
votes
1answer
148 views

How expensive may it be to destroy all long s-t paths in a DAG?

We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal ...
6
votes
0answers
129 views

EXPTIME-complete propositional satisfiability problem

SAT is NP-complete, QBF is PSPACE-complete, DQBF is NEXPTIME-complete. Is there any extension of QBF or restriction of DQBF that is EXPTIME-complete? Added later: a definition of DQBF can be found ...
1
vote
0answers
17 views

Why does there always need to be a direct crossover between parents and children in real valued GAs?

I have just been thinking about the simulated binary crossover (SBX) operator used in the NSGA-II algorithm and other real-valued genetic algorithms; and i am wondering if there is any reason that ...
2
votes
0answers
161 views

the confusion about 'with high probability (w.h.p.)'

w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that: Assuming we ...
19
votes
1answer
320 views

How to prove that USTCONN requires logarithmic space?

USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input. Reingold ...
1
vote
0answers
49 views

Computing the distribution from which this algorithm samples from

Assume we have a set of integers $X_0=\{x_1\ge x_2\ge\ldots\ge x_n\}$. Let $r\in(0,1]$ be a parameter and consider the ranking process: i=0 while ($X_i\ne\emptyset$) let $M = \max \{x\in X_i\}$ ...
25
votes
1answer
675 views

Finding a biased coin using a few coin tosses

The following problem came up during research, and it's surprisingly clean: You have a source of coins. Each coin has a bias, namely a probability that it falls on "head". For each coin ...
1
vote
1answer
128 views

Sampling distinct values with probability proportional to their frequency

This is a variant of my previous question (Reservoir sampling of distinct values) I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass ...
-5
votes
0answers
41 views

Constructing 5 qubits controlled unitary gate using no work qubit [on hold]

This is the exercise 4.28 in Nielsen&Chuang's book on quantum computation. I still have no answer for 4.28 after a hard time. The paper arxiv:9503016v1 may help. Anyone who know the answer ...
1
vote
0answers
36 views

The curve used in Parvaresh-Vardy decoding

Consider the Parvaresh-Vardy list decoder. As I understand it, the idea is to decide on a curve over an extension field of the form $(f,f^h mod E, f^{h^2} mod E,\dots)$ and then evaluate each of ...
-6
votes
0answers
33 views

Randomized Algorithm Monte Carlo Problem [on hold]

Question: Assume that candidate's intelligence is a normal distribution which will be reflected in their score during hiring interview. If a candidate score more than 7/10 then he will be hired. Given ...
1
vote
1answer
89 views

Greedy vs LP Approximation

I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, ...
2
votes
1answer
83 views

Computational complexity of modular power towers (tetration)

The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$. The complexity of modular multiplication is open though some results ...
0
votes
0answers
35 views

How dependent is complexity of trigonometric functions on the size of inputs, not just precision?

In https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Elementary_functions, computational complexity of computing trigonometric functions of type $\sin x$ to $n$-digit ...
1
vote
0answers
39 views

An Exact Cover Variant encoded in a 4-Terminal Network

During research, I hit the following problem Exact Cover Variant (ECV) Input: Three set systems $S_1, S_2, S_3$ over a universe $U$, each closed with respect to $\cap$ and $\cup$. ...
20
votes
1answer
442 views

Number of distinct differences of $\omega(\sqrt{n})$ integers chosen from $[n]$

I encountered the following result during my research. $$\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1$$ where $m=\omega(\sqrt n)$ and ...

15 30 50 per page