# All Questions

9,928 questions
3answers
2k views

### Cubic graphs and hamiltonian paths

I would like to ask, if anybody knows, whether there exists a 3-regular bridgeless graph which does not have a hamiltonian path (not necessarily extended to a hamiltonian circuit). Thank you
0answers
17 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 ...
1answer
52 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 ...
1answer
30 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 ...
7answers
3k views

### Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD). Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a ...
0answers
15 views

### Is P-complete self-reducible?

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-...
0answers
6 views

### No cyclical variable references within a for-loop = enough?

Suppose you had a machine programming language which has: Integer variables in some field $\Bbb{Z}_n$, though for small magnitude integers, this behaves completely like we're "in the integers". ...
0answers
80 views

### Could we use transcendental numbers as an RNG?

Numbers like pi and other transcendentals seem to have some nice properties, viz, we can't find patterns in them. Seems to me this could make them a nice candidate for RNGs, especially given that we ...
1answer
89 views

### Is F<: with bottom undecidable?

We all know that F<: is undecidable: http://www.cse.chalmers.se/~abela/lehre/SS07/Typen/pierce93bounded.pdf However, I have difficulties finding that anyone claiming the version with bottom added ...
1answer
63 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 ...
0answers
55 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?,...
0answers
43 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?
0answers
23 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}\}$ (...
1answer
52 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$ ...
0answers
26 views

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 ...
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 ...
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 ...
1answer
540 views

### What does “number of inputs to each neuron” mean in Neural Network terms? [on hold]

I am reading about a Neural Networks project that has some data like this I am new to this, and though I think I understand what a 3:1 network mean, I do not understand what number of inputs (to each ...
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$ ...
1answer
100 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 ...
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 ...
1answer
75 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/...
0answers
23 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 ...
1answer
202 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 ...
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 ...
0answers
37 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 ...
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 ...
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 ...
0answers
28 views

0answers
16 views

2answers
518 views

### Weakly normalizing + confluent = strongly normalizing?

I was reading this abstract and saw that they prove weak normalization and confluence. My limited understanding suggests that those two properties should provide strong normalization, which then ...

15 30 50 per page