# All Questions

9,928 questions
83 views

### Is there a method for proving non-regularity of string transformations?

There are a number of different models for defining transformations between languages. Finite state transducers and MSO-definable graph transformations over string graphs are the two that I am best ...
94 views

### Stochastic gradient methods and risk of neural nets

Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv....
67 views

### Empirical Rademacher averages versus Hoeffdings bound

Let $M$ be finite set with $n$ distinct elements. I want to probalistically approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$. An upper-bound for ...
56 views

### What forms of randomness are 'allowed' in FPRASs?

I cannot seem to find a source describing randomized approximation schemes ((F)PRAS) that tells me exactly what sort of randomness a program is allowed to use. A priori it seems to me that being able ...
1k views

### Number of words of length n in a context-free language

Denote by $w_n$ the number of words of length $n$ in a (possibly ambiguous) context-free language. What is known about $w_n$? I'm sure this has been studied a lot, but I couldn't find anything at ...
135 views

### A least sized partition of a set under a distance metric

What is the worst case complexity of an algorithm to find a least partition of a set under a distance metric, described as follows: Input: A set $S=\{s_1,\ldots,s_n\}$, where the elements $s_i$ are ...
62 views

### Complexity class of approximating perfect match count

We know we can approximate perfect matching count of bipartite and approximate volume of convex bodies in randomized polynomial time. Is there any evidence these approximations could be in Nick's ...
482 views

### Base-k representations of the co-domain of a polynomial - is it context-free?

In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open: Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for ...
142 views

### Classification of randomized approximation algorithms

Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently ...
46 views

### Lower bounds for SRM?

This question is about structural risk minimization and model selection. Let $H_n$ be the collection of all binary classifiers on some fixed set with an $n$-bit description length in some fixed ...
189 views

### Winning strategy in the game of triplets

The game of triplets is defined by a finite set of elements $X$, and a finite multi-set $T$ containing triplets of elements. Two players take turns picking elements from $X$ until all elements are ...
237 views

### Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?

A decade ago I observed what I dub "Murphy's Law of Complexity Theory": whenever a new separation or collapse is discovered, the question is answered in the direction that makes $P\overset?=NP$ most ...
167 views

### Understanding the Proof of Strong Normalization of the Calculus of Constructions

I have difficulties in understanding the proof of strong normalization for the calculus of constructions. I try to follow the proof in the paper of Herman Geuvers "A short and flexible proof of Strong ...
135 views

### Time complexity of exponentiating s-sparse matrices

Could someone suggest me a reference which discusses the time complexity of algorithms meant for exponentiating (finding $e^A$ approximately given $A$) s-sparse matrices, along with their error rates? ...
115 views

### How to write algorithms?

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
38 views

### Question About Turing Machine Computability [closed]

If p is a Turing machine then L(p) = {x | p(x) = yes}. Let A = {p | p is a Turing machine and L(p) is a finite set}. Is A computable? Justify your answer. So I'm trying to figure out how to solve ...
284 views

### Is there an algorithm that finds the forbidden minors?

The Robertson–Seymour theorem says that any minor-closed family $\mathcal G$ of graphs can be characterized by finitely many forbidden minors. Is there an algorithm that for an input $\mathcal G$ ...
153 views

323 views

### “Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes” — Worthy of arXiv.org?

Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you ...
95 views

65 views

### Libraries for programming automata and Turing machines

What are the most useful libraries around for coding related to automata and Turing machines? By useful I mean the number of functions and algorithms supported by it.
88 views

### Formal semantics of tactics

Tactics are supposed to represent inference rules in a system, and it might seem unnecessary at first to formalize the semantics of tactics; nevertheless, modern theorem provers can have pretty ...
182 views

### Equivalent formulation of complexity theory in Lambda Calculus?

In complexity theory the definition of time and space complexity both reference a universal Turing machine: resp. the number of steps before halting, and the number of cells on the tape touched. ...
68 views

### Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
44 views

### Problem property name where an optimal solution in a graph can be used as a solution in any subgraph

Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal ...
131 views

107 views

### Shortest string in the intersection of regular languages

Inspired by https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ...
645 views

### How to talk about theory

I realize this might be a contentious question, but this seemed like the right place to ask. Please redirect me if not. The background is that I am a "practitioner" (PhD student, I don't study CS ...
356 views

### What is the complexity of this game?

This is a generalization of my previous question. Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after ...
54 views

### Polynomial approximation algorithm for set cover with assumption

We want to cover $n$ elements with some sets from $S_1, …, S_m$ (classical set cover). We furthermore suppose that any element belongs to at least $k$ sets and want to find a set cover with cardinal ...
107 views

### Counting/Enumerating Minimal Edge Covers

A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it. Questions Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial ...
Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time. They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?