Reference-request is used when the author needs to know about work related to the question.
4
votes
3answers
335 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
91 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
86 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
50 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
23 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
44 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 ...
0
votes
0answers
15 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
109 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
70 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
93 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
114 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
94 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
74 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
121 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
168 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
82 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
50 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
32 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
105 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
124 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
97 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
97 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
169 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
48 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
29 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
108 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
124 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
56 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
126 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
166 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
30 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
75 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
81 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
192 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
235 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$,
...
4
votes
1answer
121 views
Tight VC bound for agnostic learning
The following result is supposedly known. However, the proofs I am able to find all prove a weaker result with an extra log factor. Where can I find the proof of the tight bound?
Theorem. Let $\...
2
votes
0answers
37 views
Is there a complete and finite axiom scheme for conditional independence? (Graphoids)
Note: This is a better-written version of an unanswered question asked before on MathOverflow.
Question: Is there a complete and finite axiom scheme for conditional probability?
If so, is ...
2
votes
1answer
107 views
What is the name of this algorithm on direct acyclic graph?
I am trying to linearize the history of a git branch for display purpose. I want commits to be collocated by branch instead of simply displaying commits in the order given by the time of commit.
In ...
1
vote
0answers
75 views
Reference request for the relationship between approximating degree of Boolean functions and learning algorithms
This paper (http://www.cs.columbia.edu/~rocco/Public/stoc01.pdf) from STOC 2001 is possibly the first paper to show how to convert upperbounds on the $\frac{1}{3}-$approximation degree of a Boolean ...
1
vote
1answer
71 views
Searching for the original definition of online algorithms
I'm currently searching for the original formal definition of online algorithms. The earliest mentions of online algorithms that I found are from the mid 80s. But none of these papers seem to be the ...
0
votes
0answers
28 views
Submodular functions over a multi-value (non-binary) domain
Classically, the domain of submodular functions is $2^{[n]}$. Is there any work with trying to extend them to domains such as $[k]^{[n]}$.
Note: I am aware of the Lovasz extension that defines them ...
3
votes
1answer
69 views
Reducing the Height of Context-Free Grammars
Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)\subseteq \Sigma^n$. In other words, all strings generate by $G$ have size $n$.
Say that a string $w\in L(G)$ has ...
12
votes
1answer
986 views
Entropy and computational complexity
There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, ...
3
votes
0answers
108 views
Practical polynomial-time implementation of bounded degree graph isomorphishm
There's a well-known article for solving graph isomorphism problem in polynomial time. Many other articles on the subject of isomorphism mention it as a possible "alternative", but note that is not ...
3
votes
1answer
154 views
Separations between testing and tolerant testing for (natural) classes of functions?
Note: I am considering here property testing in the query model, with regard to Hamming distance. (So, for instance, of Boolean functions—I'm phrasing it that way below.) I am in particular not ...
