# All Questions

11,314 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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}$)-...
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 ...
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 ...
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 ...
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 ...
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 ...
104 views

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.
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 ...
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 ...
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, ...
69 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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))...
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 ...
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, ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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. ...
### 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 ...