All Questions

-1
votes
0answers
20 views

Approximate a Decision Function Using a Neural Network

I have 10 variables $Y_i$, $i=1,\dots,10$ for a data record and I want to classify that record into one of three groups. A suggested decision function is the following: Group 1 if: $Y_i=0$ for $i=1,\...
0
votes
0answers
76 views

Something wrong with showing the limitations of finite automata [closed]

To show the limitation of finite automata (FAs) generally a non-regular language is given as an example such as $A=\{0^n1^n | n \ge 0 \}$. And it is shown that FAs cannot recognize this language. ...
6
votes
0answers
263 views

Search in a sorted matrix

A matrix $M$ is sorted if $M_{i,j}\leq M_{i+1,j}$ and $M_{i,j}\leq M_{i,j+1}$. Consider the following problem. Search in a sorted matrix Given a $n\times m$ sorted matrix $M$, where $n\leq m$....
0
votes
1answer
116 views

Data Strcuture to represent dependencies amongst modules

Consider several software modules $m_1, m_2, ... m_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in ...
5
votes
2answers
99 views

Statistical Distance Growth Given K Independent Copies

Let $X$ and $Y$ be distributions with statistical distance (total variation distance) at most $d$. What is the best upper bound you can give on the statistical distance between $k$ independent copies ...
4
votes
0answers
66 views

Refinement of the hierarchy theorem of a complexity class

Say $\mathrm{CTIME}$ is some complexity measure, syntactic or semantic (e.g. $\mathrm{DTIME}$ or $\mathrm{BPTIME}$). If we already know that for some $f(n) = \omega(n)$, $\mathrm{CTIME}(n) \subsetneq \...
3
votes
0answers
65 views

Reference request: strong polynomial-time for LP

A follow-up of sorts on this question: Complexity of finding a consistent hyperplane What is a good survey of partial results on the strong poly-time status of the general LP problem?
-1
votes
0answers
29 views

How to estimate the maximum and minimum eigenvalue of random walk Laplacian graph?

I'm wondering how to estimate the maximum and minimum eigenvalues of random walk Laplacian graph ! The normalized version of graph Laplacian allow to get eigenvalues in range [0,2]. Thank you
1
vote
1answer
63 views

Confusion about covering number

Problem I do not understand why larger $p$ will give a larger covering number. Since when $p\geq q$, the corresponding hypercube is also larger (by $\| x \| _ { q } \leq n ^ { ( 1 / q - 1 / p ) } \|...
0
votes
1answer
64 views

Question on deduction that a certain problem requires exponential space

My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space. Regular expressions with squaring are like ordinary ...
3
votes
0answers
54 views

Rearranging angles of a convex polyline to make it closed

Let {$\alpha_1, \alpha_2, ... ,\alpha_n$} be a string of n positive reals summing up to 2$\pi$. We inductively construct the following 2D polyline, denoting with $R[\alpha]$ the clockwise rotation by ...
2
votes
1answer
116 views

Generalizations of linear programming

Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs. Is there a survey/lecture notes describing ...
1
vote
1answer
94 views

Dependent C-style types with subtyping rule

I'm looking for previous work regarding an extension of a C-style type system in which types may have constraints and have a defined subtyping rule. In particular, I'm interested in defining algebra-...
0
votes
1answer
36 views

Does fixed hyperparameters perform well regardless the number of training examples?

I'm new in this community and I don't know whether my question is proper for this community. I will delete this post if it is not proper. I'm interested in deep learning network models and have a ...
2
votes
0answers
33 views

Time complexity of finding a point of infinite order on a rank 1 elliptic curve over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves over Q. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way in ...
8
votes
1answer
189 views

Depth reduction for Boolean circuits

This result by Tavenas, Koiran and others show that any polynomial computed by a circuit of size $s$ is computed by a depth-4 homogenous circuit of size $s^{\sqrt{d}}$. Are there any similar results ...
1
vote
0answers
49 views

Anagrams, Prime numbers and prime coding [closed]

I am from math.stackexchange, here is my original post. https://math.stackexchange.com/questions/2354828/anagrams-prime-numbers-and-prime-number-coding The only comment I received was too technical ...
-1
votes
0answers
14 views

Spidergon Networks-on-Chips

What do you guys think about Spidergon NoC ? Why mod 4 ? And do you guys understand how the shortest path routing algorithm depends on the value of RelAd ? The original paper : Spidergon: a novel on-...
-1
votes
0answers
31 views

total language lazy + eager term name

I have been reading a lot of works related to total functional programming and I learned that eager and lazy evaluation can be combined in such a language. However I have yet to learn of a general ...
1
vote
0answers
65 views

A question on the Kolmogorov Complexity of Human I/O behaviour

Note: From my Twitter poll I managed to get feedback from AI researchers and neuroscientists so far and I think it would be interesting to get input from theoretical computer scientists on this ...
5
votes
1answer
180 views

How to tell if an effect is algebraic?

I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic ...
1
vote
0answers
69 views

LSH Probabilistic guarantees

A family $H$ is $(r,cr,p_1,p_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have: $\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and $\lVert x-y\rVert > cr \quad \...
3
votes
0answers
68 views

Generating a random connected bipartite graph

A (n, m, k)-bipartite graph is a bipartite graphs with: independent sets of size $\{n, m\}$ a total of $k \geq n+m-1$ edges We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
10
votes
0answers
132 views

A proof of measure 1 oracle separation of $\mathbf{NP}$ and $\mathbf{PCP}(O(\log{n}), O(1))$

I came across Theorem 2 of the following paper https://www.csee.umbc.edu/~chang/papers/revisionist/rev-book.pdf by Hartmanis et. al. It states that: With probability 1, $\mathbf{NP}^A\neq \mathbf{...
3
votes
0answers
105 views

Dequantumizability known and unknown?

Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-...
4
votes
0answers
65 views

Optimal scheduling with delay constraints

Suppose you have $K$ servers numbered $\{1,2,...,K\}$. Playing server $i$ provides a value of $v_i > 0$. However, once you play server $i$, you are not allowed to play it for the next $n_i$ time-...
6
votes
1answer
215 views

Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)

In the wikipedia article on Time Complexity it is written that: The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, ...
1
vote
1answer
38 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
110 views

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

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

Why are all finite languages regular? [closed]

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
41 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
173 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
vote
0answers
239 views

On $BPP$ in $P^{NP}$ and $SETH$

It is believed showing $BPP$ in $P$ involves good $PRG$s and faces lower bound barriers. Does showing $BPP$ in $P^{NP}$ which would mean $BPP\neq EXP^{NP}$ face similar $PRG$ and give lower bounds? ...
-1
votes
0answers
21 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 ...
-2
votes
0answers
21 views

Finding all spanning trees of a directed graph

I wonder if there is a well-known algorithm (or optimized implementation) for this.
1
vote
1answer
75 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
81 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
48 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
vote
0answers
22 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 ...
3
votes
0answers
75 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
112 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/...
0
votes
0answers
36 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
115 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
56 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
22 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
45 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
232 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
67 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, ...
-3
votes
1answer
79 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
73 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 ...

15 30 50 per page