# All Questions

11,081 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: \...
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 ...
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. ...
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, ...
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 ...
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 ...
74 views

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 ...
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$ ...
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 ...
278 views

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 ...
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=...
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 ...
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, ...