All Questions
9,928 questions
9
votes
1answer
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 ...
2
votes
1answer
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....
2
votes
1answer
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 ...
1
vote
1answer
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 ...
20
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
14
votes
4answers
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 ...
5
votes
0answers
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 ...
2
votes
0answers
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 ...
7
votes
1answer
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 ...
5
votes
1answer
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 ...
8
votes
1answer
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 ...
8
votes
0answers
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?
...
1
vote
0answers
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"...
1
vote
0answers
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 ...
8
votes
1answer
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$ ...
5
votes
2answers
153 views
Typing of substitution in a bidirectional type system
In most typed lambda calculi, we have the following lemma:
If $\Gamma \vdash t_1 : \tau_1$ and $\Gamma, x : \tau_1, \Delta \vdash t_2 : \tau_2$ then $\Gamma,\Delta[t_1/x] \vdash t_2[t_1/x] : \tau_2[...
9
votes
0answers
119 views
Random unbalanced bipartite graphs are good small set expanders
My question is about small set expansion properties of random unbalanced bipartite graphs.
Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
-2
votes
1answer
116 views
Why $PSPACE!=Dtime(2^n)$? [closed]
Why $PSPACE != Dtime(2^n)$? I can not see how padding argument can help here, how can it be proven?
9
votes
1answer
128 views
Best known asymptotic PCP sizes / 3-SAT
What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am ...
0
votes
0answers
123 views
Convex mixed linear integer programming with real nuclear norm objective and linear integer objective
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
5
votes
2answers
302 views
Preservation under Substitution with Telescopes
In the simply typed lambda calculus, one can show the following result, known as "preservation under substitution":
If $\Gamma \vdash v : \tau_1$ and $(x : \tau_1) \vdash t : \tau_2$,
then $\Gamma \...
7
votes
1answer
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 ...
10
votes
0answers
95 views
Complexity of checking $a > br^m + cr^n$, with $r$ rational
I'm wondering if the following problem is decidable in P-time (or even NP):
Given $a, b, c \in \mathbb{Z}$ and $m, n, p, q \in \mathbb{N}$ all in binary, decide if $a > br^m + cr^n$, where $r = {p ...
6
votes
0answers
29 views
Locally-nameless representation: normal order & opening with a bound variable
This question concerns the representation used in Arthur Charguéraud's paper “The locally nameless representation” and is somehow a follow-up on this question, where it is asked about the ...
1
vote
1answer
80 views
A dominate vector subset sum problem
Let $k$ be some constants (e.g. one can take $k=2$ for simplexity), for any $u,v\in \mathbb{R}$, we say $u$ dominate $v$ if $\forall 1\le i\le k,~ u[i]\ge v[i]$, write it as $u\succ v$.
Consider the ...
2
votes
1answer
99 views
Minimization version of matrix p-norms?
I considered a minimization version of matrix p-norms, defined for a matrix $A$ by
$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$
Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
4
votes
0answers
47 views
Formalization of Interval Newton methods in a proof assistant or theorem prover
I am undertaking the task of formalizing Interval Newton Methods in Isabelle. To the best of my knowledge this hasn't been formalized in other proof assistants or theorem provers. However, I want to ...
1
vote
1answer
237 views
$P=BPP$ without good PRGs?
We know that the existence of good pseudorandom generators (PRGs) does not only imply $P=BPP$, but also $PromiseP=PromiseBPP$.
Let us assume $PromiseP\ne PromiseBPP$. Then good PRGs do not exist. ...
6
votes
1answer
107 views
All-or-Nothing Single-Sink Flow Problem
I have a problem where I want to find the maximum flow from $s$ to $t$, such that, for an edge $e \in E$, $f(e) = 0$ or $f(e) = c(e)$. Where $f(e)$ is the flow in the edge and $c(e)$ its capacity. ...
5
votes
1answer
106 views
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total ...
1
vote
0answers
63 views
Missing proof in Salil Vadhan's monograph on pseudorandomness, Random Walks and S-T Connectivity
In Salil Vadhan's monograph on pseudorandomness, chapter 2, half of the proof of Lemma 2.51 is missing
http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf .
I don't state the full lemma ...
-4
votes
1answer
49 views
Ordering of sub problems in dynamic programming
1) Can every dynamic programming question be solved using 3 different orderings or can there be more than 3 or less than 3 ( like unique ordering )?
My understanding is that a) it might have a unique ...
8
votes
1answer
160 views
Type theory and computational complexity
Is there a type system, which restricts the lambda terms to the terms which fall inside a complexity class? Like the typable terms in the theory are strictly inside the complexity class ? Or is it not ...
13
votes
2answers
623 views
Automata learning without counterexamples
In Angluin's automata learning framework, a student aims to learn a regular language $L\subseteq \Sigma^*$ by asking two types of questions to his teacher:
Word queries: given $w\in \Sigma^*$, is $w\...
4
votes
0answers
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.
5
votes
2answers
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 ...
7
votes
3answers
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.
...
4
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
131 views
Smallest disjoint union chain containing a sequence of sets
Let $\mathcal{A}=\{A_1,\ldots,A_n\}$ be a family of sets, we have the property that $A_1=\emptyset$, and one can obtain $A_i$ from $A_{i-1}$ by adding or deleting a single element.
A family $\...
2
votes
1answer
91 views
Sample Complexity for Order Statistics
I have a sample complexity question which seems fairly basic, but for which I'm having trouble finding a reference.
Let $F$ be an unknown distribution over $[0,1]$. Denote by $X_{k:n}$ the $k$th of $...
9
votes
0answers
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 ...
17
votes
3answers
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 ...
10
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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 ...
1
vote
0answers
20 views
What is the maximal load of a “latency-bounded” Cuckoo Hash?
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 ...
17
votes
1answer
2k views
Algorithm whose running time depends on P vs. NP
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?