All Questions

0
votes
0answers
3 views

Extending EAL with recursion makes it incompatible with the abstract algorithm?

A few years ago, I've asked if Elementary Affine Logic can be used as the core type system of a practical programming language. The accepted answer argues that, yes, although such language would be ...
0
votes
0answers
53 views

Can be converted UNAE3SAT into a P-complete decision problem?

By Self-reducibility, we understand that a search problem can be reduced to the self problem but by a decision problem instead of a function problem. P is trivially self-reducible, but what about P-...
0
votes
1answer
42 views

Why are all finite languages regular? [on hold]

It is said that "All finite languages are regular". But the Pumping Lemma says that, if a language is regular one can find a 'large-enough' word w such that it can be decomposed into w = xyz such ...
-1
votes
0answers
26 views

Counting class for DP problems

What would be the corresponding counting complexity class for decision problems in $DP$? Recall that $DP:=\{\mathcal{L}_1\cap\mathcal{L}_2\mid \mathcal{L}_1\in\text{NP},\mathcal{L}_2\in\text{coNP}\}$ (...
3
votes
1answer
87 views

What are CS blogs for puzzles/games?

I am looking for blogs which contains recent progress on puzzles/games (Algebraic and Combinatorial) etc. like Soduko, latin square etc. I come across a list on TCS What CS blogs should everyone read?,...
-1
votes
0answers
49 views

On derandomizing $BPP$ problem

It is believed derandomizing $BPP$ to $P$ involves good PRGs and faces lower bound barriers. Does derandomizing to $P^{NP}$ face similar issue or is there evidence that it is vastly easier?
-2
votes
0answers
26 views

The maximum-weight subgraph problem, NP-hard? approximation?

Input: a graph $G=(V,E)$ and a weight $w_{ij}$ (possibly negative) for each edge $i,j\in V$. For each vertices $i$, there is an edge to itself, i.e., $w_{ii}$ may not be zero. Output: find a subset $...
-1
votes
0answers
16 views

Is this a correct way to prove the inapproximability of general k-center?

Claim: for any polynomial time computable function $\rho (n)$, the k-Center problem cannot be approximated within a factor of $\rho (n)$, unless $P=NP$. k-CenterDecision Problem: given a complete ...
-1
votes
0answers
17 views

Finding all spanning trees of a directed graph

I wonder if there is a well-known algorithm (or optimized implementation) for this.
0
votes
1answer
55 views

About learning a single Gaussian in total-variation distance

I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown! Let $G$ ...
0
votes
1answer
68 views

Lower bound of real valued bounded function

Is well known that the lower bound on number of example necessary to reach a given error for concept classes $\Omega(d/\varepsilon)$ (cf. also Agnostic PAC sampling lower bound ) I am looking for ...
0
votes
1answer
27 views

Bi-criteria combinatorial approximation algorithms for min k-vertex cover

Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized. It is easy to ...
-1
votes
0answers
30 views

Nondominated Sorting Tradeoff Curves [on hold]

Let vector a = (0, 0, 0), b = (1, 1, 1), c = (-2, 0, 3). Each index in the vector represents an objective. We wish to minimize the objectives. By this we get: Vector a dominates b because every ...
1
vote
0answers
19 views

Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?

I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that $G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$. $G$ has no left recursion; that is, we can't ...
-2
votes
0answers
22 views

Complexity of a Subset Sum variant with target dependent on elements

I would like to know whether the following problem is NP complete: For a set $S = \{(a_1,b_1,\delta_1),\ldots,(a_n,b_n,\delta_n)\}, a_i,b_i,\delta_i \in \mathbb{N}$. Does $\exists ~S^{'} \subseteq S$ ...
3
votes
0answers
62 views

Is monotone 1-in-3 MAXSAT known to be APX hard?

Monotone 1-in-3 SAT is the problem where each clause of the SAT problem contains exactly 3 positive variables. The goal is to find an assignment such that exactly one variable is true in each clause ...
3
votes
1answer
79 views

Is there a simple algorithm for proof search on CoC?

Given the usual Calculus of Constructions with an extra primitive, _, that stands for "attempt to fill this location in a way that type-checks", is there any simple/...
-1
votes
0answers
26 views

Encoding naturals in the calculus of constructions and in a language like Idris

I'm learning some type theory and trying to relate that to what I already know about proving things in Idris and similar languages. So, if I were to encode natural numbers in CoC, I'd probably have ...
3
votes
1answer
101 views

Solving Feedback Vertex Set (FVS) in FPT time $5^k$ with iterative compression?

I understand that Disjoint Feedback Vertex Set (= looking for a solution $X$ of size $k$ given a solution $W$ of size $k+1$ s.t. $X \subseteq V \setminus W$ ) can be solved in time $4^k poly(n)$, see ...
-1
votes
0answers
50 views

Is there any approximation factor for this algorithm?

I have a very specific question which has baffled me for a while. Assume we are given a set of pairs of integers, $T = \{(x_1,y_1),...,(x_N,y_N)\}$. We want to find a set of $k$ groups each ...
-1
votes
0answers
20 views

What makes MLT-3 better than B8ZS encoding?

In class today, my teacher explained the history of transmission of data for the internet, through cables, and how different encodings have been developed to guarantee that no clock skew occurs and ...
1
vote
0answers
39 views

Sketching order statistics of a stream

Suppose we have a string stream over alphabet $[n]$. At each step, we would like to compute a sketch of the last $k$ elements, such that from the sketch we can approximate their relative order. For ...
9
votes
1answer
203 views

What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based ...
0
votes
0answers
65 views

Where is the flaw in this proof that an LP solves TSP? [duplicate]

In this preprint on Arxiv, M. Diaby, M.H. Karwan, and L. Sun give a Linear Program which they claim solves the Traveling Salesman Problem. In contrast to their prior work, which was asked about here, ...
0
votes
0answers
28 views

Derive quantum state (bloch sphere) [closed]

I read "Quantum Computing and Information" book. On the page I found that equation (*): $$ |\psi \rangle = \alpha |0 \rangle + \beta|1 \rangle $$ can be rewritten as: (**) $$ | \psi \rangle = e^{i \...
-3
votes
1answer
72 views

Are there any known languages in the intersection of NP and co-NP but not in P? [closed]

We currently don't know the relationship between NP and co-NP, but would it be possible to show whether the intersection is equal to P? I can't think of any languages in both NP and co-NP, but not in ...
1
vote
1answer
61 views

Name for a special family of languages?

I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$: $\mathcal{F}$ consists ...
-1
votes
1answer
106 views

Why does the Placid Platypus function grow faster than any computable function?

I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (...
0
votes
0answers
22 views

Computing a sum of products of ratios of QAP-like functions

Let $A \in \{0,1\}^{n \times n}$ be a binary symmetric matrix, and let $\sigma : [n] \to [n]$ denote a permutation on $[n] = \{1,\dots,n\}$. Let $S_n$ be the set of these permutations. Let us write $A^...
0
votes
1answer
84 views

Definitional equality of recursive function definition by “infinite unfolding”

The context is checking definitional equality in dependent type theory implementations. Consider in Coq ...
-4
votes
0answers
60 views

Is there any problem that cannot be solved in O(n!) time? [closed]

In other words, does a problem exist such that if we try to compute a solution it, then it's running time grows faster than n! (factorial of n)? If it does exist, give me some examples and if it doesn'...
-1
votes
0answers
16 views

Eigenvalues of almost Laplacian matrix, particular structure

I have a square matrix of the form: \begin{pmatrix} a&b \\ -b&a \end{pmatrix} where $a = \begin{pmatrix} D1&t&0&0&t&0 ... \\ t&D2&t&0&0&t... \\ 0&...
2
votes
1answer
72 views

Oncina-Garcia RPNI algorithm for learning DFAs

The question refers to this paper: ftp://altea.dlsi.ua.es/people/oncina/articulos/asspr1992.pdf Given a sample of $p$ positive and $n$ negative strings, RPNI constructs a consistent DFA in time $O((p+...
1
vote
1answer
70 views

Computational hardness for sampling a uniform matching

A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one ...
3
votes
0answers
57 views

Proof that CIC or Dybjer-style eliminators are strongly-normalizing?

Related to this question I'm wondering, what is the standard technique for showing that dependent types with eliminators are strongly normalizing? I'm thinking something like the Calculus of ...
7
votes
1answer
146 views

P and Descriptive Complexity

In the Complexity Zoo, it says [1] that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$. However, ...
1
vote
0answers
90 views

Parallel building time of a k-d tree on n points with n processors

Given a point set with $n$ points to build a k-d tree on. We have $n$ processors available. What is the time-optimal building time for the k-d tree? A straight forward parallelization would be as ...
0
votes
0answers
43 views

$k$th element in data stream

In the streaming model how can i find the $k$th element (not $k$th most frequent) with erorr of at most $\pm \epsilon$ s.t. we return index $i$ that $(1-\epsilon)k \leq i \leq (1+\epsilon)k$ using ...
6
votes
0answers
113 views

Can reciprocal inputs speed up monotone computations?

A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
2
votes
1answer
135 views

An equation relating Time complexity, Space complexity, and entropy of output

Is there an equation that relates minimum time complexity, minimum space complexity, and entropy of the output of a function? It seems to me that there should be a relatively intuitive relationship ...
-2
votes
0answers
41 views

How many succinctly generated circuits are there for a given circuit size?

How many circuits are of size $n$ are there? In general for a size $n$ circuit, I know there are $O(2^{poly(n)})$ circuits$^1$, but surely this is reduced by the succinctness condition? $^1$ https://...
-2
votes
1answer
95 views

Does P^NP=NP imply NP=coNP? [closed]

If you have it, the proof would be appreciated. Note: P^NP means P with NP oracle
1
vote
0answers
21 views

whether two sets of stabilizer generators are related by a Clifford circuit

I have two stabilizer models each specified with a given set of generators. Let's call the two generating sets $S_1$ and $S_2$. By stabilizer model, I mean putting the generators on unit cells of a ...
-1
votes
0answers
48 views

Taylor Series relationship to Neural Networks

I've started learning Machine learning, more specifically Neural Networks. I had learned previously that any analytic function can be approximated with a Taylor Series with the error being quantified ...
6
votes
1answer
147 views

Infinite process balls in bins problem

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
8
votes
4answers
287 views

List of quantum-inspired algorithms

Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra: A quantum-inspired classical ...
2
votes
0answers
65 views

Best algorithms for real linear programming

Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of ...
3
votes
0answers
69 views

Is it possible to check equality of equi-recursive types, or recursive λ-terms?

Can we determine if two λ-terms are equal? Given two lambda terms, let's say they are equal if their (possibly infinite) Bohm trees are. Under this definition, for example, ...
2
votes
0answers
60 views

Complexity of counting Wang tiles

Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?
-2
votes
0answers
58 views

How low can $NC$ be?

If $P=PSPACE$ then what is the best collapse possible for $NC$ class?

15 30 50 per page