Reference-request is used when the author needs to know about work related to the question.
7
votes
1answer
305 views
Proof techniques for showing that dependent type checking is decidable
I'm in a situation where I need to show that typechecking is decidable for a dependently-typed calculus I'm working on. So far, I've been able to prove that the system is strongly normalizing, and ...
5
votes
1answer
164 views
Boolean circuits which correspond to L/poly
Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$.
Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
8
votes
1answer
122 views
What's the difference between Moggi's computational metalanguage and Moggi's lambda calculus?
This is a reference confusion. Sometimes I see people use the term "Moggi's computational metalanguage" to refer to the calculus presented by Moggi, and sometimes to "Moggi's computational lambda ...
4
votes
3answers
117 views
Complexity of isotopy of embedded graphs
I am looking for previous work on the following problem: given two graphs embedded in the plane without crossing, determine if they are isotopic. By isotopic I mean that there is a continuous ...
3
votes
2answers
108 views
Examples/Textbooks on amortized analysis of algorithms
I am trying to get the amortized analysis for a complicated algorithm. I am wondering whether there are textbooks or illustrative examples that could serve as inspiration of techniques in amortized ...
-1
votes
1answer
61 views
How to know if a problem is distributable?
I am new to the world of Parallel computing and that is why don't know exactly where I should look at or search to get the answer.
Is there any theorem or just general theory determining which code ...
15
votes
0answers
402 views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
9
votes
2answers
136 views
Decidability of type inference and type checking in MLTT
In Martin-Löf's An Intuitionistic Theory of Types: Predicative Part it is proved that type checking $a \colon A$ is decidable subject to $a$ being typeable in the first place, by proving a ...
5
votes
1answer
247 views
Is there a useful notion of being “approximately computable”
It seems that we can define a notion of being “approximately computable” where a set, $S$, is approximately computable if there is a family of computable functions $f_n(x)$ such that $$\lim_{n\to\...
5
votes
3answers
436 views
Sorting a programs instructions until it works
Lets say I have a computer program below.
(define (factorial x)
(if (= x 0)
1
(else (* x (factorial (- x 1)))))
I then take each line of the ...
3
votes
1answer
103 views
Rademacher complexity for piecewise-linear convex function
Consider a function family $$\ell(x)=\max_{1\leq k\leq K} a_k^\top x + b_k,$$ where $a_k,b_k \in \mathbb{R}^d$ are bounded in the sense of some norm and $K\geq 2$. What is the best upper bound on the ...
9
votes
0answers
97 views
Graphs with minimal-size induced subgraphs
I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is $d$-...
6
votes
0answers
58 views
Reference request: transforming a grammar to Greibach normal form preserves the number of parse trees
I believe that most "natural" ways of transforming a grammar to the GNF should preserve the number
of parse trees for each string. For example, Urbanek's construction from the paper
"On Greibach ...
1
vote
0answers
24 views
Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent
I am aware that convergence in stochastic gradient problems is very sensitive to the variance of your gradient estimator. One issue I'm running into is that the gradient is a random vector and so ...
2
votes
0answers
48 views
For each edge, find a matching that containing it and has maximum weight
Given a weighted graph $G=(V,E)$. For each edge $e\in E$, we are interested in finding a maximum weight matching over all matchings that contains edge $e$.
If $G$ is bipartite, then this can be done ...
13
votes
0answers
246 views
Algebraic topology for termination proofs
I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings...
From the ad-...
0
votes
0answers
16 views
Any reference on the hardness of Monroe rule for the case of Borda satisfaction function?
I'm considering the computational hardness of winner determination under two well-known rules, i.e., the Monroe and Chamberlin-Courant rules. Skowron et al. have mentioned in Achieving fully ...
4
votes
2answers
122 views
Max cut problem between two connected subgraphs
Let $G$ be a connected graph.
Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known ...
4
votes
1answer
80 views
Exact algorithm or parameterized algorithm for Maximum Edge Biclique Problem?
The Maximum Edge Biclique(MEB) problem is to find a biclique with as many edges as possible in a bipartite graph. It was proved to be NP-complete by Peeters in 2003, and then the inapproximability ...
9
votes
0answers
95 views
Expected value of the evaluation of Boolean circuits of depth $2n$
I am not an expert on circuits and I wonder whether the following problem was already studied (and possibly solved). Any reference or suitable method to solve this question would be welcome.
Let $C_{...
7
votes
1answer
122 views
Another planar separator ref question
Do any of you know a reference for the following (surprisingly tedious to prove) result?
Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \...
4
votes
1answer
106 views
Fast algorithm to find a maximum connected subgraph of k vertices
Given an undirected graph $G = (V, E)$ and a function $f: 2^V \to \mathbb{R}^+,$ where $2^V$ is the set of all subsets of $V$. Find a connected subgraph $T = (V_T, E_T)$ of k vertices such that $f(V_T)...
3
votes
0answers
81 views
Critical Assignments vs Read-Once Branching Programs - Reference Request
Straight to the point:
I'm looking for a reference for the fact that the complexity of a read-once branching program solving the search problem for an unsatisfiable formula $F$ is at least the ...
8
votes
0answers
151 views
Have people looked for parameterized algorithms for problems that are not in NP?
Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the ...
7
votes
2answers
173 views
Communication complexity of approximating the size of set intersection
Consider the set-intersection problem: Alice and Bob each get a subset of $\left\{ 1,\ldots, n\right\}$, and they would like to know whether their sets intersect. This is a canonical problem of ...
6
votes
1answer
86 views
The originator of the fixed point theorem for DCPOs
Pataraia proved in
"A constructive proof of Tarski’s fixed-point theorem for dcpo's", presented in the 65th Peripatetic Seminar on Sheaves and Logic, in Aarhus, Denmark, November 1997
that in a ...
1
vote
0answers
56 views
Directed NP Hard Problem on DAG
There are problems that are NP-Hard on undirected graphs(maximum weight independent set and graph coloring) but are polynomial time solvable on trees. Tree decomposition is a good tool to talk about ...
1
vote
0answers
38 views
maximization of non-negative monotone supermodular set function with cardinality constraints
the following link Maximizing a monotone supermodular function s.t. cardinality says no kind approximation possible for maximizing non negative supermodular function subject to maximum cardinality ...
2
votes
0answers
108 views
BQNC and Abelian Hidden Subgroup Problem
We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous.
Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$? If not what is it that makes integer factorization special?
In ...
6
votes
1answer
136 views
How to solve this generalization of binary search?
Let $f:\{1,\ldots,n\}$ be a monotonically non-decreasing function.
Consider, for some unknown threshold $1\le T\le n$, a threshold function
$$g(x)= \begin{cases}
0&\text{x<T}\\
1&\text{...
5
votes
0answers
98 views
Reduction between functions that preserves time and space-complexity
Under which reduction(s) is the class $\mathsf{FTISP}(t(n), s(n))$ closed?
Let $\mathsf{FTISP}(t(n), s(n))$ the class of functions from $\{0,1\}^*$ to itself that are computable by a Turing machine ...
5
votes
0answers
98 views
Seminal papers related to SMT theories (particularly QF_ABV)
I am working on an application using Quantifier-Free Bit-Vector/Array satisfiability which may or may not require mucking around with the internals of an SMT solver, and would like to understand what'...
0
votes
1answer
50 views
What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph?
I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of
Counting the number of distinct s-t cuts in a oriented graph
It says ...
9
votes
0answers
170 views
Regular expressions of prefixes/suffixes
It is well-known that star-free regular expressions, which are defined by the grammar
$r::= a \mid r \cdot r \mid r \cup r \mid \neg r \mid \varepsilon \mid \emptyset$
where $a$ belongs to a finite ...
1
vote
0answers
50 views
Relative Two-Function Hypercontractive Inequality $\langle T_{\rho\sigma} f,g \rangle \le \langle T_{\sigma} f,g \rangle^q$
The hypercontractive theorem (or Bonami Beckner inequality) says (Ryan O'Donnell):
This of course also directly gives the 'intermediate' inequality $\|T_{\rho\sigma}f\|_q \le \|T_\sigma f\|_{1+(q-1)\...
3
votes
0answers
34 views
$p$-biased two-function hypercontractivity
The Hypercontractivity theorem (or Bonami Beckner inequality) is a very useful tool. Unfortunately, it isn't easy to carry over to other spaces than the uniform boolean cube.
In Ryan O'Donnel's ...
3
votes
1answer
110 views
Tighter Probability Bounds
Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are ...
0
votes
0answers
42 views
Memory failure computation
Is there any research into models of computations with failures? For example, a Turing machine tape that stores the correct value with a certain probability? Or the cell has a certain probability of a ...
3
votes
2answers
128 views
Reference request: Skeptics of classical threshold theorm
Early classical computing had skeptics, or at least cautious researchers, that were skeptical reliable computing results were possible. Scott Aaronson references this in a page on his site:
A: The ...
3
votes
1answer
107 views
Results/concepts that also proved useful outside of their “home areas”
There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used ...
4
votes
1answer
57 views
Relation between OSAs and grammars
Are there any relation between order-sorted algebra (OSA) and grammars (context-free grammar in particular)?
If I'm not mistaken, according to [1], there is an equivalence between order-sorted and ...
6
votes
0answers
128 views
Has what I am calling “helpfulness” here been studied?
We say that a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ is helpful for another Boolean function $g$ if $f(x)$ can be computed with a smaller circuit given $g(x)$ as an extra input bit. I'...
1
vote
0answers
58 views
What is the fastest gradient based algorithm to get to criticality of a “nice” non-convex function?
I am allowing for the following properties for a once differentiable non-convex $f : \mathbb{R}^d \rightarrow \mathbb{R}$,
(a) Let there be a $\sigma >0$ s.t the norm of the gradient of the ...
2
votes
1answer
168 views
P vs. NP in a logic with a random oracle
Choose a random oracle $f : \{0,1\}^\ast \to \{0,1\}$, and define the logic $ZFC^f$ by adding a fresh symbol $g$, an axiom that $g$ has the correct type, and one axiom $g(s) = f(s)$ for each $s \in \{...
1
vote
0answers
31 views
Getting to local/global minima with (stochastic) gradient descent on non-convex objectives
Is there any class of non-convex objective functions for which (stochastic) gradient descent can provably get to a local or a global minima? (..maybe in the approximate sense like a point such that ...
3
votes
1answer
76 views
Reference Request: soundness in a ZKP achieved by walking along a doubly-stochastic Markov chain?
Consider the following variant of a zero-knowledge proof that two graphs, $G_1$ and $G_2$, given by adjacency matrices $M_1$ and $M_2$, respectively, are not isomorphic.
Here Peggy the prover wants ...
1
vote
0answers
84 views
Purely spectral algorithms for the minimum spanning tree problem
There are many algorithms that address the MST problem, from classical (Boruvka, Prim, Kruskal), optimal (Pettie et al.) to their distributed variants (Bader et al.).
However, I fail to find any ...
6
votes
1answer
202 views
Are there works on “quantum parametrized complexity”?
I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. I don't know if researchers in quantum complexity have started using ...
11
votes
1answer
238 views
Parameterized complexity of inclusion of regular languages
I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed ...
6
votes
0answers
207 views
Fischer and Rabin's theorem (1974) for theories of “additive” structures
Fischer and Rabin's Super-Exponential Complexity of Presburger Arithmetic (1974) has the following theorem.
(Theorem 12) Let $U$ be any class of additive structures, so if $A = (A, +) \in U$,
...
