-2
votes
0answers
26 views

Sorting a subset of a sorted set; does it need the merge sorting complexity?

Suppose that we have an algorithm in which we have a sorted list of objects like $L = (x_1, x_2, \ldots, x_n)$ (the indices denote the order of the objects). During the algorithm we have a loop where ...
3
votes
0answers
63 views

NP-Complete Static Square Puzzles

In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to ...
4
votes
0answers
55 views

Expander Graph from Hypergraph

I came up with this problem while thinking about an optimizing compiler. Let $H$ be a hypergraph. From this we construct a graph $G_H$ as follows the vertices are the hyperedges of the hypergraph. ...
5
votes
0answers
58 views

Direct Proof that the Pigeonhole Principle is Hard for Regular Resolution

It is well known that the pigeonhole principle $PHP_n^{n+1}$ is hard for general resolution. The original proof due to Haken is elegant. One first defines a complexity measure for derived clauses, in ...
-1
votes
0answers
48 views

Is this problem involving shortest paths NP hard?

A graph with positive edges is given along with several vehicles at specific vertices of the graph.One of the vehicles has a package that is required to be transferred to a destination node.The ...
1
vote
1answer
39 views

A coupon collector type problem with changing probabilities

Suppose we are flipping coins starting at some time $t$. At time $t$ the probability we obtain heads is $\frac{1}{\sqrt{t}}$. If the coin lands tails, at time $t+1$ the probability of heads is now $\...
-1
votes
0answers
29 views

How to randomly sample a social graph to find paths between at least 20% of profiles?

Given a Graph, where we know Total number of nodes (~100,000) Average no of connections per node (~200) Maximum distance between two nodes (~5) How many nodes (and its connections) do we have to ...
-2
votes
0answers
38 views

Channel capacity as a limit on information storage

It is well-known that Shannon's channel capacity provides an upper bound on the amount of information (measured in bits/s) that can be reliably (i.e. with vanishing decoding error probability) ...
9
votes
1answer
101 views

Linear circuit complexity classes

The class $\textrm{NC}^i$ is the class functions computable by circuits families of bounded fan-in, $n^{O(1)}$ size and $O(\log^i(n))$ depth. The $\textrm{NC}$-hierarchy is the union of those classes....
2
votes
0answers
46 views

Linear optimization over intersection of totally unimodular matrices

I am currently dealing with a problem of the following form \begin{alignat}{2} &\underset{x, y \in \mathbb{R}^n}{{\text{min}}} && e^T x \nonumber\\ &\text{sub to} \hspace{0.05in}&&...
10
votes
1answer
724 views

Number of 4 cycles

Let $C_4$ be a cycle with four vertices. For an arbitrary graph $G$ with $n$ vertices and m edges say $m>n\sqrt n$, how many $C_4$s exist? Is there a lower bound for this?
3
votes
2answers
370 views

Is there a non-deterministic version of the complexity class PP?

From a quick skim of the literature (and complexity zoo), there doesn't seem to be a non-deterministic version of PP. Is there a reason for this (e.g. PP=non-deterministic PP?) Edit: Perhaps I ...
1
vote
0answers
38 views

Average margin bounds for separable SVM

Suppose we're training a linear separator in the realizable PAC setting. Given $m$ labeled examples $(x_i,y_i)$ in $\mathbb R^d\times\{-1,1\}$, a (consistent) linear separator is a vector $w\in\mathbb ...
8
votes
1answer
186 views

Is algorithmic information theory still evolving?

I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory. The field seems very interesting for me, but it seems everything is the field was done ...
6
votes
0answers
85 views

Complexity of fractional SAT

Let $(a, k)$-SAT be $k$-SAT with the promise that if there is there is a satisfying assignment, then there is such an assignment that satisfies at least $a$ literals of every clause. Can 3-SAT with $...
7
votes
0answers
107 views

Relatively low ambitious frontiers

What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing? For example: In the draft version of Arora ...
-1
votes
0answers
30 views

Recovering full ordering from partial ordering [closed]

Suppose there $n$ object with the total ordering. We want to recover the ordering using partial orders. If we are given $\alpha $% uniformly selected random subset of the partial orders, what are ...
5
votes
0answers
121 views

Optimal set union tree

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
-1
votes
0answers
30 views

What is the correspondence between the category theory and the tree structure? [closed]

I am looking for similarity between objects in OO programming and category theory. In my current understanding, a set can be similar to a list of objects of the same type. Some people say that ...
-1
votes
0answers
68 views

Quantum attack on classical hash functions [closed]

Consider a classical hash function that gives $x\rightarrow c = H(x)$, where $c$ is a commitment. I know how to program $H$ on a classical computer so I write the quantum circuit, $U$, for it. $\...
6
votes
1answer
298 views

Proof techniques for showing that dependent type checking is decidable

I'm in a situation where I need to show that typechecking is decidable for a dependently-typed calculus I'm working on. So far, I've been able to prove that the system is strongly normalizing, and ...
-4
votes
0answers
27 views

The big question: does P=NP? [migrated]

I figured it was a shame that one of the biggest open questions in theoretical computer science was not listed here as a question. True, nobody has an answer (probably), but still. Some might argue ...
1
vote
1answer
50 views

Sample complexity for learning Boltzmann Distribution parameters

I am trying to think through the number of samples that I would need to estimate the parameters of a Boltzmann partition function to a desirable precision. Suppose that there are N possible states ...
-4
votes
0answers
16 views

Convert grammer in to Greibach form [closed]

The grammer is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an npda accpeting language generated by this grammer but for that i firstly need to convert it into greibach form....
-2
votes
0answers
54 views

Equivalence relations with DFAs [closed]

I'm taking a theory computation class and we've just learned how to formally define a DFA (the 5-tuplet). I'm having difficulty understanding how to manipulate $δ^∗$ in order to prove the equivalence ...
0
votes
0answers
31 views

Efficient topological sorting of the cartesian product of DAGs

Let us consider n directed acyclic graphs $(G_i)_{1\leq i \leq n}$ and G their cartesian product (with the induced edges) : G is still a DAG. Let us suppose that each vertex has a value, defined as ...
1
vote
0answers
148 views

Automated theorem proving PhD

I'm looking for a university where I can do doctoral studies in automated theorem proving / computational algebra. Any ideas? Thank you!
-3
votes
0answers
41 views

Is bounded-error quantum polynomial time (BQP) class can be polynomially solved on machine with discrete ontology?

What is your opinion and thoughts about possible ways to get an answer whether problems that are solvable on quantum computer within polynomial time (BQP) can be solved withing polynomial time on ...
0
votes
0answers
8 views

Is the problem of determining whether a CFG generates a string in the form 0*1* decidable? [migrated]

Given a grammar G, is it decidable whether G generates any string in the form 0*1*? Why? I think it's undecidable but can't find any undecidable problem to reduce it to.
0
votes
0answers
40 views

Function that maps non-linear distribution to normal distribution while maintaining distance

I have a collection $X$ of 10 million $(x,y,z)$ 3-tuples, where $x$, $y$, and $z$ are all numbers between 0 and 1. The distribution of $x$, $y$, and $z$ values are complex, and the distributions of $...
4
votes
1answer
161 views

Boolean circuits which correspond to L/poly

Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$. Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
1
vote
1answer
61 views

Color shifting in a bipartite graph

Assume that we have a directed bipartite graph $G = \langle L\dot\cup R, E\rangle $. Where $E$ contains directed edges only from $L$ to $R$, that is, $E\subseteq L\times R$. Assume further that the ...
6
votes
0answers
160 views

How many different proofs are there of parity is not in AC0?

The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part ...
2
votes
0answers
25 views

Heuristics for exact #3COLORING close to the 3-colorability threshold

What are some fast heuristics for exactly counting 3-colorings of graphs close to or at the 3-colorability threshold? Is there literature on the average-case performance for any of these methods?
8
votes
0answers
213 views

L/quasipoly vs NL/poly

Savitch's theorem shows that NSPACE($S(n)$) $\subseteq$ SPACE($S(n)^2$), which means that nondeterminism can be replaced by more spaces in this situation. Is it known whether nondeterminism can be ...
0
votes
0answers
28 views

How should a reduction to the Cardinality Constrained Quadratic Knapsack Problem work?

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
6
votes
2answers
229 views

Algorithm for identifying unprovable statements

I understand that this may depend on the specific set of axioms, but is there a general way (algorithm) for automatically detecting unprovable statements within a set of axioms? For example: If there ...
2
votes
1answer
92 views

Circuit complexity of group actions

Suppose that $G$ is a group with $|G|=n$. Suppose that $G$ is generated by elements $g_{1},\dots,g_{k}$. Let $\iota:G\rightarrow S_{2^{N}}$ be an injective group homomorphism such that $\iota(g_{i}):\{...
8
votes
1answer
114 views

What's the difference between Moggi's computational metalanguage and Moggi's lambda calculus?

This is a reference confusion. Sometimes I see people use the term "Moggi's computational metalanguage" to refer to the calculus presented by Moggi, and sometimes to "Moggi's computational lambda ...
7
votes
1answer
177 views

TIME(n) versus TIME(nlogn)

The time hierarchy theorem implies TIME($n$) is strictly contained in TIME($n\log^{1+ε}n$) for all ε>0. Is the relationship between TIME($n$) and TIME($nlogn$) known?
-1
votes
0answers
14 views

Matrix to Multi-level security [migrated]

How to convert access control matrix to Bell-LaPadula. Can teach me step by step What best way to control converting Bell-LaPadula Model lattice using Access Control Matrix Matrix GIVEN $\quad\quad\...
6
votes
0answers
89 views

Efficient quantum algorithm for CLASSICAL FFT

Is there a known improvement on the current O(n*log(n)) algorithm for CLASSICAL FFT using quantum computation? 'n' is the number of samples. I need to find the amplitude and phase of the K dominating ...
3
votes
1answer
93 views

Does a non-constructive proof of bounds of a computable asymptotic complexity, with impossible fix, exist?

Does there exist an algorithm, about which a non-constructive $\omega$-consistent theory $A$ can prove that it has time complexity $O(f(n))$ where $n$ is some univariate function of the input, but ...
2
votes
0answers
72 views

Counting the maximum number of paths of length $n$ that differ in at least $k$ edges

What is known about the complexity of solving (or approximately solving) the following problem? INPUT: Graph $G=(V,E)$ and constants $L$ and $K$. OUTPUT: The maximum size of any set $S$ of simple ...
2
votes
3answers
158 views

Is it reasonable to allow the type of a λ/∀-bound variable to refer to itself?

Usually, in Pure Type Systems, the type of a λ/∀-bound variable is only accessible on its body. That is, on λ (X : A) -> B, <...
1
vote
0answers
47 views

Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity

I am wondering if this is a topic that has had research done... If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...
2
votes
0answers
87 views

Complexity of solving a polynomial equation

Given a polynomial equation of degree n with m variables, that is guaranteed to have at least one solution, what is would be the ...
-2
votes
0answers
68 views

Converting a propositional formula into an equisatisfiable CNF

For my homework I am asked the following question and determine whether it is true or false: Converting a propositional formula into an equisatisfiable CNF formula in the worst case requires ...
3
votes
2answers
142 views

How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

AIC-based model-selection converges to zero error in the limit, and also has finite-sample convergence that is rate-optimal with respect to worst case minimax error [1]. (Note that AIC refers to ...
-1
votes
0answers
29 views

Proof of equivalency of URM machine and Davis machine

How to prove that URM machine and Davis machine are equivalent? Or how to generate any symmetry between them?

15 30 50 per page