# All Questions

10,256 questions
Filter by
Sorted by
Tagged with
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
2k views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
94 views

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> ::= &...
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: ...
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, ...
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-...
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 ...
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 ...
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 ...
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 ...
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.
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, ...
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 ...
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 ...
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$ ...
406 views

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 ...
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 ...
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 ...
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}$ -...
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 ...
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 ...