All Questions

Filter by
Sorted by
Tagged with
4
votes
1answer
265 views

Why is regularity a problem in cubical type theory?

In my current understanding, regularity in cubical type theory is the following definitional equality: $$ \cfrac{A~\textbf{type} \quad a:A} {\text{transport}(\langle i \rangle A, a) \mapsto a} $$ I am ...
1
vote
0answers
32 views

Obtaining a lower bound of a matrix norm

I was wondering (on a setting where $\vec X_i \sim \mathcal{N}(\vec\mu, \mathbb{I})$ are $n$ random $d$-dimensional multivariate normal vectors with unknown mean $\vec\mu$) how I could obtain a lower ...
-4
votes
0answers
40 views

What can a complexity theorist do to learn modern machine learning?

Complexity theorists deal with the fundamentals of computation and strive for the limits to perfection in computation. They have been trained to think differently from normal computer science ...
-2
votes
0answers
21 views

Stratified K-fold Cross Validation and PCA, which one should be done first?

I'm recently approaching Data Mining and Machine Learning. I have been asked to learn a classifier from a Training Set using the 5-fold Cross Validation; specifically, I want to learn a Random Forest ...
-3
votes
0answers
84 views

$K$ Disjoint Triangles [closed]

Given an undirected graph $G$ and a parameter $k$, the task is to decide if there exists a collection $C$ of $k$ vertex-disjoint triangles. We need to create a randomized algorithm in O*($2^{3k}$)-...
-3
votes
0answers
83 views

What is a complexity class? [closed]

From Wikipedia, "Complexity classes are sets of related computational problems. They are defined in terms of the computational difficulty of solving the problems contained within them with ...
0
votes
1answer
82 views

Calculus of constructions: Why forall when pi exists?

I'm studying the calculus of constructions from ATAPL, Chapter 2. I'm trying to understand the Type Equivalence rule, which describes the meaning of the new type family ...
-4
votes
0answers
22 views

Two weights with different MSA [closed]

Give an example of a digraph D = (V; A), a root r, and two weight functions w1 and w2, such that w1(e1) < w1(e2) if and only if w2(e1) < w2(e2), for every e1, e2 in E, yet the minimum-weighted ...
-2
votes
0answers
27 views

How to perform imperical performance evaluation to my algorithms (Online-Tetris)? [closed]

Ciao, I created algorithms to play and solve Tetris Problem. My problem is I am not sure how can I perform some empirical performance evaluation on them. In offline algorithms, this is easy as we only ...
1
vote
1answer
123 views

Characterization of integral polyhedra

A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$. Equivalently, $P$ is integral if ...
5
votes
1answer
104 views

Definitional function extensionality for functions out of $\mathbf{2}$

Denote by $a$ and $b$ the canonical terms of $\mathbf{2}$. For any map $f:\mathbf{2}\to \mathcal{U}$ we have the eliminator$$\mathrm{ind}_{\mathbf{2}}(f) : \big(f(a) \times f(b)\big) \to \prod_{x:\...
-2
votes
1answer
55 views

Linear Integer Arithmetic Satisfiability with Three Literals

I'm stuck on trying to find an unsatisfiable conjunction of the form $a \wedge b \wedge c$ where: $a \wedge b$ is satisfiable $a \wedge c$ is satisfiable $b \wedge c$ is satisfiable $a, b, c$ are ...
0
votes
1answer
96 views

What does x.y notation mean?

In Harper's PFPL (Ed. 2, top of page 8), this notation is used but I don't see a definition. What does $x.y$ mean?
4
votes
0answers
76 views

Simple randomized priority queue matching the Fibonacci heap time bounds?

Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.). Many classical worst-case ...
6
votes
1answer
98 views

Finding vertex separator such that the induced subgraph has minimal number of edges

My problem is related to edge and vertex cuts with a little twist. Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that ...
-3
votes
0answers
18 views

role of DML Pre-processor as component of DBMS?

On multiple sites and books I have read this role of DML preprocessor. DML preprocessor converts DML statements embedded in an application program into standard function calls in the host language. ...
1
vote
0answers
72 views

Take a natural quotient of context-free grammars

Fix a finite alphabet. Let $\mathrm{CFG}$ be the set of context-free grammars on this alphabet, $\mathrm{CFL}$ the set of context-free languages, $\mathrm{UG}$ the set of unrestricted grammars and $\...
3
votes
0answers
62 views

Useful notion of ambiguous growing context-sensitive language

As far as I understand there is no useful notion of ambiguous context-sensitive language. For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
2
votes
0answers
312 views

The implication of $ S(SAT)=2^{\Omega{(n)}} $ Conjecture (5.7 in Wigderson Book)

I started to read Avi Wigderson book Math and Computation, which get me excited about the following: Conjecture 5.7. $ S(SAT)=2^{\Omega{(n)}} $, where $S$ denotes the size of the smallest Boolean ...
-4
votes
0answers
39 views

Extending Turing machine to Operators

So far based on my understanding, Turing machines essentially computes recursing function on numbers. Now I was wondering if its possible to extend the propertied of Turing machine operators, i.e. it ...
-3
votes
0answers
53 views

Reduction of CNF-SAT to 3-dominating set [closed]

I don't understand Lemma 2.1: http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf "Suppose S has two (or more) partial assignment nodes from the same clique. Then there is some clique for ...
3
votes
0answers
90 views

SVM perturbation bounds

Let $B$ be the unit ball of $\mathbb{R}^d$. Suppose that $x_1,\ldots,x_n$ are vectors in $B$ with labels $y_i\in\{-1,1\}$. We say that $w\in B$ separates this labeled set with margin $\gamma$ if $y_i(...
4
votes
3answers
235 views

Proving proof system properties within the proof system itself?

While reading about Frege proof systems in [1], I came across the completeness theorem and its proof, which involves a few lemmas introduced first. Here are the first two of those lemmas: $$\begin{...
-1
votes
1answer
122 views

What are the known classes of undirected graphs such that every graph belonging to that class is guaranteed to have a Hamiltonian Path?

One trivial class of graphs is the class consisting of complete graphs or complete bipartite graphs with equal sized partitions. I would love to know if more such classes exist.
-2
votes
1answer
84 views

upper bound on the total number of fixed-length paths in an acyclic graph [closed]

I was wondering if there is an upper bound on the total number of fixed-length paths (path length from 1 to $n-1$ given $n$ nodes) in an acyclic graph (not directed) of $n$ nodes? If so, can you point ...
3
votes
0answers
158 views

HyperLogLog: Why “Hyper?”

I was teaching the HyperLogLog estimator in class earlier this week and a student asked where the “hyper” bit came from. I know that HyperLogLog is a refinement/improvement to the LogLog estimator, so ...
2
votes
2answers
167 views

Are there strongly normalizing lambda terms that cannot be given a System F type?

I know that all well-typed System F terms are strongly normalizing, but is the converse true as well? In other words, does System F typeability precisely characterize program termination? (And if so, ...
2
votes
1answer
69 views

Covering a binary relation as a union of rectangles

Given finite sets $X$ and $Y$ and a subset $R\subset X\times Y$, I want to express $R$ as a union $R=\bigcup_{i=1}^n X_i\times Y_i$ with $n$ as small as possible. Here, each $X_i\subset X$ and $Y_i\...
0
votes
0answers
47 views

Dynamic programming algorithm to find a colorful subset of disjoint sets

Suppose there is a set $F=\{X_1 ,...,X_m\}$, such that $\forall 1\leq i\leq m: |X_i|=3.$ Suppose we color the elements of $\bigcup F$ in $3k$ colors. We wish to know if there is a subset $F'\...
-1
votes
2answers
61 views

Pi-type over a list in dependent type theory

In a formalization I need to create an inductive type which has a term for each element in a list, something like this (I'll use Agda in the following, but everything here is standard dependent type ...
2
votes
1answer
38 views

Relative error estimation of a special type of GapP function

Consider the functions included in the complexity class GapP. We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly ...
3
votes
1answer
124 views

Are uniqueness rules converse to introduction rules?

I've seen many people connecting introduction rules and elimination rules, saying that they're dual notion. Indeed, like in the categorical model, these rules are symmetric morphisms. However, if we ...
0
votes
0answers
50 views

Efficiently checking if removing a vertex yields a connected partition

Having seen the answer here, I have been looking at the algorithm suggested by Chlebikova (1996). The algorithm needs an implementation of the blockbalance algorithm which requires that one repeatedly ...
1
vote
0answers
33 views

program search with optimization methods for (resource bounded) Kolmogorov complexity

Are there fields of research that look at finding short programs for generating strings (therefore trying to find the (resource bounded) Kolmogorov complexity of the string), but using optimization ...
2
votes
2answers
336 views

Proving not NP-complete by non-existence of gadget

Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if ...
1
vote
0answers
46 views

sophistication or logical depth to detect intelligent extra-terrestrial species

From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
-1
votes
0answers
32 views

k packing problem

In packing problems, we need to select a set of sets of items, such that no item is chosen twice (in Set−Packing, the actual items must not be packed twice, in Graph−Packing the copies of the graph ...
-3
votes
0answers
122 views

Are space and time hierarchies infitesimally graded?

Space(n) is in nspace(n) which is in space (n^2) and I get refinements in. https://en.wikipedia.org/wiki/Space_hierarchy_theorem#Refinement_of_space_hierarchy. What is smallest f(n) so that space(f(n))...
4
votes
1answer
158 views

Does such a bipartite graph exist?

In the course of my studies on graphs I sometimes use gadgets. I recently came upon a need for a certain bipartite graph with the following properties, and I am wondering if anyone knows if such a ...
-2
votes
1answer
110 views

Where, if any, is there currently any research being done on the subject of ternary computers? [closed]

I had the experience several years ago of working with a team that had developed a ternary computing system. It ran out of funding and was abandoned but I felt it was ahead of its time. Currently, ...
3
votes
0answers
55 views

Using Baire Category to analyze the efficiency of the Simplex Method

I read from the wiki page of the Simplex Algorithm that we can "use Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the ...
3
votes
1answer
92 views

Hardness when restricted to an infinite number of far apart instance sizes

Is there a result that rules out (under common complexity theoretic assumptions) that one can solve an NP-hard problem in polynomial time for an infinite number of possibly very far apart instance ...
0
votes
1answer
78 views

Reference for context-free grammar for Martin-Löf type theory

Are the terms and the types of Martin-Löf type theory described by context-free grammars? Have such grammars been written down somewhere?
0
votes
0answers
74 views

Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

Crossposted at MathOverflow A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$. $\mathbf{1}$ is ...
4
votes
0answers
153 views

What kind of research can be considered publishable for undergraduate or graduate students (MSc level)

I'am currently doing a non-research Dipl.Eng (Engineering Diploma in French school system equivalent to MSc) in Computer Science. The courses I am currently taking are software oriented, there's an ...
-3
votes
0answers
93 views

When does complementariness imply lowness?

We know $NP=coNP$ implies $NP=PH$. However $PP=coPP$ does not imply $PP=CH$. However $NL=coNL$ forbids $NL$ hierarchy. $PL=PL^{PL}$ has nothing to do with $PL=coPL$. I. Why does $PP=coPP$ does not ...
0
votes
0answers
160 views

Understanding a conference reviewer comment

I submitted my first paper to ICALP 2021 and just got the reviews back after receiving a rejection a couple of days ago. The reviews were overall positive with nearly all of the comments on ...
16
votes
4answers
3k views

Algorithms Careers

I’ve been writing software for a living for a number of years now. I have graduate background in mathematics and I am wondering whether knowledge of higher algorithms is utilized anywhere in industry. ...
0
votes
0answers
76 views

Kleisli-like category for applicatives?

I am wondering if there is a good way to complete the following analogy: monad : Kleisli category :: applicative functor : ?? That is, a given monad T on a ...
0
votes
0answers
180 views

An $O(n^2\log^c{n})$ algorithm for matrix multiplication in this paper?

In the newest version of this paper by Yijie Han, the author claims that matrix multiplication can be solved by an $\tilde{O}(n^2)$ algorithm. It should be a big result, but it is still in arxiv and ...

15 30 50 per page
1
2 3 4 5
227