All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
1 view

This theorem: L2= { W E {a I b} * : no prefix of w starts with b}

L2= { W E {a I b} * : no prefix of w starts with b} = { W E {a, b} * : the first character of w is a} U {e} Why is it in union with an empty string? If an empty string from b can also be a prefix.
7
votes
2answers
128 views

How long does it take to find a short cycle in a random graph?

Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges. With very high probability, $G$ has many $4$-cycles. Our goal is to output any one of these $4$-cycles as quickly as ...
4
votes
3answers
127 views

Can Non-termination be considered an algebraic effect?

Non-termination is sometimes considered an effect. I have been reading about algebraic effect systems (What is algebraic about algebraic effects and handlers?), and I suspect non-termination (like ...
4
votes
2answers
81 views

What category are Tagless Final Algebras final In?

The Haskell and Scala community have been very enamored recently with what they call tagless final 'pattern' of programming. These are referenced as dual to initial free algebras, so I was wondering ...
31
votes
5answers
12k views

Complexity of the simplex algorithm

What is the upper bound on the simplex algorithm for finding a solution to a Linear Program? How would I go about finding a proof for such a case? It seems as though the worst case is if each vertex ...
-1
votes
0answers
17 views

Why computable functions defined on natural numbers, is there an alternative?

I am not completely sure that why computable functions is defined as a subset of all functions from/to Natural Numbers, but as far as i know, computation comes from real (physical) world so ...
4
votes
2answers
299 views

Colouring achieving simple discrepancy bound?

Given a hypergraph $H$ with $n$ vertices and $m$ edges, one of the simplest inequalities on the discrepancy of $H$ is $\text{disc}(H) \le \sqrt{2n \ln (2m)}$. This is usually proved by mixing ...
453
votes
70answers
160k views

What papers should everyone read?

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different. We all have favorite papers in our own respective ...
57
votes
15answers
2k views

Open access journals

With the advent of internet (and common sense) there is more and more demand for open-access research. Several researchers (including me) find it frustrating that published peer-reviewed research ...
10
votes
3answers
328 views

When is the duality gap of semidefinite programming (SDP) zero?

I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold? For example, when one goes back and forth ...
0
votes
0answers
25 views

Attacks on Niederreiter cryptosystem

Guo et al presented an attack on QC LDPC McEliece cryptosystem. Before that, a similar attack was presented on QC MDPC in Asiacrypt by Guo et al. Do these attacks also work on Niederreiter ...
21
votes
10answers
2k views

#SAT Solver download

Could anyone please point to one or more websites where is possible to download a working implementation of a #SAT solver? I'm interested in those returning the exact solution count, not an ...
2
votes
1answer
57 views

Reconstruction of a sequence generated by a Markov chain - reference request

Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols ...
4
votes
1answer
63 views

Terminology and references for a learning model

Let's say we're doing regression over $[0,1]^d$ -- either in the PAC sense with bounded-range agnostic noise or in the more classical-statistics sense with additive Gaussian noise. Suppose further ...
8
votes
0answers
175 views

Conditional separations of $\exists\mathbb{R}$ from $\mathbf{PSPACE}$

As pointed out explicitly by Emil Jeřábek here: Even with Turing reductions, $\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$ would still be a breakthrough (and completely unexpected) result. So ...
-2
votes
0answers
14 views

On definition and study of software delivery algorithms and related computational complexity

Recent developments around software delivery automation (often related to as continuous integration/devops) have emphasized on standardization of phases required to deliver software, differing though ...
8
votes
2answers
147 views

“Relatives” of the shortest path problem

Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such ...
9
votes
0answers
94 views

Is unary $\Pi_2$-SUBSETSUM coNP-complete?

Consider the following problem: for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation define is it true that for every $S \subseteq \{1, ..., 2n \}$ such that $|...
52
votes
5answers
5k views

What kind of answer does TCS want to the question “Why do neural networks work so well?”

My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to ...
5
votes
0answers
70 views

Are there languages require many variables to achieve $\Sigma_n^0$ completeness?

The proof of Post's Theorem that I am familiar with assumes you have access to as many variables as you wish in your language. Matiyasevich's Theorem by contrast gives a $\Sigma_n^0$-complete formula ...
5
votes
0answers
145 views

Martingale exit arguments for gradient Langevin dynamics

I am concerned about the proof of Lemma 6.3 (page 18) of this paper, https://arxiv.org/pdf/1902.08179.pdf which shows that for smooth convex functions the gradient Langevin dynamics has a high ...
-1
votes
0answers
47 views

Total number of trees where non-leaf nodes have at least 2 children

Given $N$ leaves, how many trees can be constructed if every non-leaf node has at least 2 children? Below are the 30 trees given $N=5$: Additionally, if we account for the order of $X_1,X_2,X_3,X_4,...
0
votes
0answers
52 views

Transforming Lambda Calculus syntax into generic relations between finite strings

I am trying to validate the simplest possibly notion of a formal system as relations between finite strings. I know that Lambda Calculus has the expressive power of a Turing Machine: <λexp> ::= &...
216
votes
58answers
86k views

Major unsolved problems in theoretical computer science?

Wikipedia only lists two problems under "unsolved problems in computer science": P = NP? The existence of one-way functions What are other major problems that should be added to this list? Rules: ...
-1
votes
0answers
51 views

Is there a Turing machine that limit-compute if some other TM halts on all inputs? [closed]

The halting problem can be stated by the decision problem "does the Turing machine $T_n$ without input halts?". It is undecidable, however the binary sequence of the solutions of the halting problem, ...
-1
votes
1answer
109 views

Evidence integer multiplication is in linear time?

After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
-1
votes
0answers
47 views

Diagram of relations between different branches of mathematical logic and type theories

There are many forms of various mathematic logics, lambda-calculus, satisfiability modulo theories, category theories, type theories, including HoTT and Cubic HoTT, and so on. Lambda cube is a famous ...
-3
votes
0answers
31 views

Find all interval weights in a DAG [on hold]

I found this interesting problem in Jeff Ericksons Book Algorithms but couldn't solve it yet and I'm not sure how close I am (http://jeffe.cs.illinois.edu/teaching/algorithms/book/06-dfs.pdf) For ...
-2
votes
0answers
18 views

Generating random path between two vertices in a directed graph

I want to generate a random path between two vertices in a directed graph with self-loops and multiple edges. Is there any existing algorithm which does such a thing? I would like the generation ...
2
votes
0answers
107 views

Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
3
votes
2answers
156 views

What is the best approximation and exact algorithm for vertex cover on cubic graphs?

"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
40
votes
21answers
4k views

What hierarchies and/or hierarchy theorems do you know?

I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, ...
18
votes
5answers
2k views

Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?

It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$. This can easily be understood inductively using oracle machines. The question ...
3
votes
0answers
52 views

Enumerating Minimal (a,b) vertex separators in a DAG

A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components. $S$ is a ...
3
votes
2answers
617 views

An upper bound for chi-square divergence in terms of KL divergence for general alphabets

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ ...
8
votes
2answers
406 views

PPAD and Quantum

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
-1
votes
0answers
15 views

Which error should be used to show pruning vs error

I trained a model using mnist and cross entropy and I also done pruning on the trained model. I want to know if I draw a graph or evaluate the performance of test or train model which error/ loss ...
33
votes
3answers
4k views

Evidence that matrix multiplication cannot be done in O(n^2 poly(log(n))) time

It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here. I have asked some people who are ...
0
votes
0answers
38 views

Volume computation of special polytopes

I'm interested in computing the volume of a special class of $\mathcal{H}$-polytopes and the complexity of doing so. I know that in general it is #P-hard to compute the volume of $\mathcal{H}$ -...
2
votes
1answer
74 views

Correlation between noise resilience and output distribution of Boolean circuits

Given a randomly generated AND/OR tree (and negations), we can calculate the probability that the circuit will represent a specific Boolean function up to 3 input literals. Starting from 4 (or at ...
3
votes
1answer
90 views

Satisfiability problems with restricted (not bounded) number of occurrences per variable

Intro It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly ...
1
vote
0answers
48 views

Lossless vs lossy compressible bin sequences

What are some interesting differences between the set of lossless and lossy compressible binary sequences (lossy := there exists a decompression algorithm that can recover over 50% of the sequence’s ...
7
votes
0answers
194 views

Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$. Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$. $\mathsf{...
5
votes
1answer
133 views

Complexity of DFA intersection in this specific case?

In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible ...
7
votes
1answer
113 views

Example of a function that you can write in Calculus of Constructions but not in System-F

It's been suggested in an answer to this question that the Calculus of Constructions has more computational strength than System-F. What are examples of functions that you express in CoC that you ...
-2
votes
0answers
16 views

2-Clustering of a graph to minimize the maximum intra cluster edge length

I have a complete graph $G(V, E)$. I want to partition $V$ into two clusters such that maximum intra-cluster edge length gets minimized. What is the fastest algorithm that solves this problem?
2
votes
1answer
136 views

Why is differential privacy defined over the exponential function?

For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies $$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ ...
4
votes
0answers
147 views

Is my understanding regarding how to implement Quotient Types correct?

I was trying to understand Quotient Types, and determine if Self-Types can be used to implement them. From a Reddit post, Here is an example and explanation that may be more familiar to non-...
0
votes
0answers
52 views

When can convex optimization be considered to be exactly solvable?

If one is trying to find the global minima of a convex function using gradient descent then one will get a run-time which is a function of $\epsilon >0$ where $\epsilon$ measures the accuracy of ...
2
votes
1answer
97 views

Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free

What is the relationship between graphs which have $O(\log n)$ treewidth and $\mathcal{H}$-minor-free graphs? Are graphs which have $O(\log n)$ treewidth $\mathcal{H}$-minor-free? I know that graphs ...

15 30 50 per page