All 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?

15 30 50 per page