All Questions
11,081
questions
0
votes
0answers
3 views
What is congruence in lambda-calculus
I see a lot of lecture notes where the terms "congruence" (ex: congruence relation) or deriving usages such as "the expression e is alpha-congruent to e2".
Could someone please ...
0
votes
0answers
10 views
Different definitions of grammar complexity
It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
0
votes
0answers
7 views
Optimum partitioning of vertices into mutually disjoint subsets in a weighted graph
tl;dr I'm trying to partition my students into groups with respect to their preferences, i.e. they can declare if they want to be with someone in a group or if they do not want to be with someone in a ...
0
votes
0answers
32 views
Are maximum independent set and minimum clique cover also cover-packing problems?
Maximum independent set and minimum edge cover are a pair of related problems and are cover-packing problems. (Also see p114 of West's Introduction to Graph Theory)
Are maximum independent set and ...
0
votes
0answers
17 views
Are Graph Databases computationally equivalent to relational algebra
I am wondering if it can be shown that graph databases along with the graph database model and cypher queries are computationally equivalent to relational algebra. More specifically can cypher queries ...
-3
votes
0answers
9 views
Help find algorithm for array-based task
Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i < j и a[i] > 2a[j]. How to count number of interesting pairs in O(nlogn)?
What is the solution?
My solution is not ...
6
votes
2answers
100 views
Why should we believe that $NEXP \not \subset P/poly$
I am sorry if this is not an advanced question. Most computer scientists believed that $Nexp \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...
2
votes
1answer
42 views
Tableau method for two-variable first-order logic
$FO^2$, i.e. two-variable first-order logic, has a NEXPTIME-complete satisfiability problem (see Grädel, Kolaitis and Vardi '97). However, the decidability and complexity of this fragment is proved by ...
0
votes
0answers
20 views
A variant of randomized co-ordinate descent
Let us consider the following optimization problem.
$\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that ...
-3
votes
0answers
57 views
Complexity implications of impossibility of direct Diffie-Hellman compromise
Given generator $g$ of a multiplicative group mod a prime $p$ the Diffie Hellman problem is to find $$g^{xy}\bmod p$$ from $g^x\bmod p$ and $g^y\bmod p$. The best way to solve this is through discrete ...
1
vote
0answers
46 views
Hardness of Approximation of Continuous Metric k-Median
First let me describe the metric $k$-median problem.
Definition (Metric $k$-Median): Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ ...
-2
votes
0answers
57 views
How could we implemented orthogonality with Miranda, Haskell, Julia, Scheme, and Erlang languages? [closed]
How is orthogonality implemented with Miranda, Haskell, Julia, Scheme, and Erlang languages?
9
votes
0answers
211 views
NP complete problem help
I'm currently trying to find a reduction to this problem:
Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
0
votes
0answers
31 views
Internal as well as external partition of (regular) graphs
Let $G$ be a simple finite undirected graph. Let $\{V_1,V_2\}$ be a partition of its vertex set; that is, $V_1\cup V_2=V(G)$ and $V_1\cap V_2=\emptyset$. The partition $\{V_1,V_2\}$ is said to be an ...
1
vote
0answers
51 views
Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains
Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...
4
votes
1answer
57 views
Context weakening as an explicit rule for languages of the the lambda cube?
I'm trying to formalize the syntax and typing judgments of the Calculus of Constructions in Coq. I'm choosing to use the Pure Type Systems presentation of CoC; however, I've seen mild variations in ...
-3
votes
0answers
35 views
A variant of the Generalized Assignment problem
There are two sets $T$ and $M$. The set $T$ represents a set of tasks and the set $M$ consists of machines. A task $t_i \in T$ has two attributes: 1) a minimum-finish requirement $R_{t_i}$ and 2) an ...
-3
votes
0answers
26 views
What changes the output on this black box?
We have a theoretical black box with no obvious inputs and outputs a value. For the sake of imagination, it's a literal black box with a digital counter on one side. We want to figure out what causes ...
0
votes
0answers
32 views
Hardness of Approximation for Hypergraph Vertex Cover for Non-constant $k$
A $k$-uniform hypergraph $H = (V, E)$ consists of a set of vertices $V$ and a collection of edges $E$ of $k$-element subsets of $V$ called hyperedges. The hypergraph vertex cover problem asks for a ...
0
votes
0answers
74 views
Optimal $\ell^1$ sketching, including the coefficient
Let us define the sketch as mapping $\varphi:R^D\to R^d$, such that for arbitrary $x\in\mathbb{R}^D$, its $\ell^1$ norm is preserved up to $\epsilon$ error, with $1-\delta$ success probability:
$$\...
2
votes
0answers
38 views
Energy-Based Modeling vs Deep Learning
I am doing some research on machine learning algorithms in the context of a seminar, which focuses on Energy-Based Modeling vs Deep Learning specifically in working with images Modeling. Now I know ...
-3
votes
0answers
60 views
Lower bound for SAT
It occurred to me that if a given SAT is unsatisfiable, then a DPLL algorithm must try true/false settings for all literals to determine that there does not exist any satisfying literal combination. ...
1
vote
1answer
67 views
Dynamic transitive closure with immediate new reachability facts
The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, ...
-1
votes
2answers
90 views
Knowing if there are two solutions to the subset sum problem
I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are ...
3
votes
1answer
198 views
Formalization of simulation for Turing machines
Right now I am trying to understand the concept of simulation in theoretical computer science, focussing on Universal Turing machines. All textbooks that I looked into only explain examples. They ...
-1
votes
1answer
74 views
What is the time complexity of computing intersection and union of Nondeterministic Finite Automata (NFAs)?
Assume that $\mathcal{A} = (Q_A, \Sigma, \Delta_A, q_{i_A}, F_A)$ and $\mathcal{B} = (Q_B, \Sigma, \Delta_B, q_{i_B}, F_B)$ are two NFAs. What is the worst-case time complexity of computing $\mathcal{...
7
votes
0answers
77 views
Is it possible that feedback vertex set problem has an $O(k^2/\log k)$ kernel?
(This question also suits for other similar natural $\mathrm{NP}$-hard problems)
I know that there is a $4k^2$ vertex kernel (and $8k^2$ edge kernel) by Thomasse [Thomasse09] for Feedback Vertex Set (...
1
vote
0answers
196 views
Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?
Underlying motivation for the question: if someone showed that $\text{P}=\text{NP}$ but the algorithm thus produced for, e.g., $3\text{-SAT}$, runs in time $\Omega(n^G)$ where $G$ is Graham's number, ...
3
votes
0answers
61 views
Suffix array construction algorithms (SACAs)
I am working on an efficient pattern-matching algorithm (using binary files as input) based on suffix arrays. I would like to ask you If you are familiar with any suffix array construction algorithm (...
9
votes
1answer
73 views
What are the general direction and target question in the field of quantum error correction?
After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
0
votes
1answer
101 views
When does a bipartite graph have bounded treewidth?
As the title says, I want to know when the treewidth of a bipartite graph is bounded by a constant. What families of graphs are both bipartite and bounded treewidth?
More generally, I would like to ...
5
votes
2answers
207 views
Intuition behind nested positivity and counterexamples
I'm looking at the nested positivity conditions for inductive types stated in the Coq manual. First off, are there any other references (not necessarily for Coq, but in dependent type theories ...
0
votes
0answers
33 views
Online Weighted Allocations to Simulate a Distribution
I have a seemingly simple task that I want to solve using an online algorithm but unfortunately I wasn't able to find relevant resources even though it seems so basic.
The inputs are $D=(d_1,\dots,d_m)...
-4
votes
0answers
51 views
Under what name is that NP-Complete commonly known? [duplicate]
When I was a student, I was explained a problem that fascinated me, and at this time, I was told it's an NP-complete problem - which I ended up reducing to a combinatory problem according to notes I ...
0
votes
0answers
29 views
what is the LP gap of this particular non metric facility location problem in planar graphs?
Suppose I have a facility location problem with all service costs 0 (or infinity (in particular service costs are not metric)) such that the edges $ij$ for which facility $i$ can service client $j$ ...
2
votes
0answers
40 views
Computational complexity problem book with solution recommendation?
I will be taking complexity class next quarter and we will use the book "B. Barak, S. Arora, Computational Complexity: A Modern Approach". However, I have little exposure to complexity ...
12
votes
2answers
278 views
Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings
We say that a pair $(P,N)$ of subsets of strings from $\{0,1\}^n$ is an $n$-pair if $|P|=|N|=n$. Intuitively, sucha a pair consists of a set $P$ with $n$ positive $n$-bit strings, and a set $N$ with $...
5
votes
1answer
68 views
Survey on Quantum error correction
Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of ...
6
votes
1answer
78 views
Nonterminal descriptional complexity of regular languages
Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below.
I am aware of an ...
15
votes
2answers
915 views
Proof relevance vs. proof irrelevance
I want to use use Agda to help me write proofs, but I am getting contradictory feedback about the value of proof relevance.
Jacques Carette wrote a Proof-relevant Category Theory in Agda library. But ...
12
votes
2answers
398 views
One-way randomized communication complexity of Greater-Than
Let $\mathrm{GT}_n:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ be the greater than function: $\mathrm{GT}_n(x,y)=1$ exactly when the positive integer whose binary representation is $x$ is greater than the ...
1
vote
1answer
92 views
Why isn’t information-probability relationship linear? [closed]
I am completely new to information theory.
I was learning about information content but couldn’t make sense of why the relationship between information content and probability isn’t linear? And why it ...
1
vote
0answers
28 views
Are there classes where all Eulerian orientations can be listed in polynomial time?
Is there is a subclass of regular graphs (say 4-regular graphs) for which there is a polynomial time algorithm to list all Eulerian orienations?
An Eulerian orientaiton of an (undirected simple) graph ...
4
votes
1answer
96 views
Minimal clique edge cover vs minimalist (assignment-minimum) ones
Given a graph $G=(V,E)$, a clique edge cover is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \...
3
votes
0answers
91 views
(Integer) Linear Program formulation of planarity?
Q: Is there an efficient (I)LP formulation of planarity?
More specifically, I am looking for a set of constraints that are satisfied by exactly all planar graphs on $n$ vertices, in order to optimize ...
-2
votes
0answers
22 views
Explanation of Minimap2 Algorithm [closed]
Can someone provide a concise explanation of Minimap2 algorithm on how it is used in pairwise alignment?
Here is the paper: https://academic.oup.com/bioinformatics/article/34/18/3094/4994778?login=...
2
votes
0answers
84 views
Can someone recommend a reference on graph minors structure theorem and sublinear treewidth?
Can someone recommend a reference on graph minors structure theorem and sublinear treewidth? Doesn't have to be the newest/strongest results as long as it's easier than tracking down all the papers ...
22
votes
2answers
1k views
Decidability of diophantine equations over {=, +, gcd}
It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, ...
-3
votes
0answers
89 views
Do these examples belong to syntax or semantics and are they handled by syntactic or semantic analysis?
In the dragon book
4.3.5 Non-Context-Free Language Constructs
A few syntactic constructs found in typical programming languages cannot be speci ed using grammars alone. Here, we consider two of
these ...
-4
votes
0answers
100 views