Questions tagged [reference-request]
Reference-request is used when the author needs to know about work related to the question.
0
votes
0answers
21 views
What is the right term/theory for prediction of Binary Variables based upon their continuous value?
I am working with a linear programming problem in which we have around 3500 binary variables.
Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
2
votes
1answer
225 views
Is there a counterexample to this work?
Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...
1
vote
0answers
33 views
A categorized (?) list of functional pearls in JFP and ICFP
Is there a list of (categorized preferred) functional pearls ever published in ICFP and JFP? I could go to the ICFP proceedings and JFP issues and find all of them, but this would be time-consuming.
...
2
votes
0answers
45 views
Problems and theories in CS that uses Fibonacci numbers
I want to know problems and theories where Fibonacci sequence is used and where we have some possibility to use Fibonacci numbers. I have found that-
In counting number of steps for Euclidean ...
8
votes
2answers
205 views
Hereditary substitution with a universe hierarchy
I've read about hereditary substitution for the Simple Lambda Calculus and for The Logical Framework with distinct terms and types.
I'm wondering, are there any examples of hereditary substitution in ...
6
votes
1answer
150 views
Does Max Planar 3-SAT admit a PTAS?
Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
1
vote
1answer
368 views
Possible to do Complexity theory with only counting and Pigeonhole
Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient ...
5
votes
0answers
138 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
67 views
randomly sample a degeneracy ordering
Given an undirected graph $G$, the $k$-core of $G$ is defined as the maximal subgraph such that each vertex has at least $k$ neighbors in the subgraph. The cores of $G$ can be computed by the ...
9
votes
1answer
125 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 ...
5
votes
2answers
277 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 \...
9
votes
1answer
377 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
175 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
143 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
121 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
121 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
64 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
409 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
142 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
256 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
441 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
108 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
62 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
26 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
248 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
129 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
84 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
123 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
123 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
82 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 ...
10
votes
0answers
176 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
175 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
90 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
62 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
44 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
118 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
139 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
99 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
101 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
51 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
174 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
51 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
38 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
120 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 ...
7
votes
2answers
202 views
Reference request: Skeptics of classical threshold theorem
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 ...
