# Tag Info

5

This was shown by Hardy in his monograph Orders of Infinity.

5

These colleagues of yours, would they happen to be Haskell aficionados? They might have told you that Hask was a category made from Haskell, but that is a lie, notheless a very useful one that inspires new programming techniques. If you would like to find out how category theory informs functional programming, I can recommend Bartosz Milewski's Category ...

4

Your problem, solving a system of linear equations, can be solved using an ancient algorithm, Gaussian elimination, which works over all fields. Note that linear programming is more general, allowing also inequalities. It is not entirely clear, however, how the order should be defined over a finite field.

4

My favorite is Understanding Machine Learning: From Theory to Algorithms. It’s presentation is very probability oriented and introduces concepts in a very concise, yet insightful way. It covers the foundations of a lot of Statistical Learning Theory and thanks to the rigorous introduction, I found it is easy to build on certain directions that interest me.

3

From the first line of Wikipedia's GNFS page: "the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than" The following factorizations of RSA numbers used none other than the GNFS algorithm: February 2020: RSA-250 December 2019: RSA-240 February 2020: RSA-232 August 2018: RSA-230 May ...

3

Given a graph, does it have a cycle of length $3$ ($4$)? Four-cycles there is an easy algorithm that requires $O(n^2)$ time. The best known algorithm for triangle detection is related to matrix multiplication and has complexity $O(n^\omega)$ where $\omega$ is the matrix multiplication exponent. It is an open problem to determine whether $\omega=2$. Given a ...

3

(Answered also on https://cstheory.stackexchange.com/questions/47691/) A ($2C_4$, $C_5$, $P_5$)-free graph may have exponentially many maximal cliques. For example, the complement of the disjoint union of $n/3$ triangles with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ appear as an induced subgraph. https://doi....

3

This answer assumes that you only allow the tiles to have integer sides. There are always some trivial tilings, in which the rectangle being tiled has either a single row or a single column. Counting the number of these is simple combinatorics. Let us show that deciding whether there are any other tilings is NP-complete (under randomized reductions, or ...

2

In 1966, I was taught by Professor Tom Kilburn at Manchester University. He said the half adder was sometimes called the Kilburn adder because he invented it!

2

The essential problem is that most files are NOT compressible (see the counting argument). And an already compressed file is much less likely to be compressible.

2

There probably are automated ways of doing it, but the result will be a unreadable mess. You have to understand what the imperative program is doing and rethink it as a functional program. Not easy. The point is that many imperative algorithms have a recursive idea behind them (think binary search, mergesort, quicksort, any tree walking), there it is ...

2

This is essentially the same problem as partition. Let $M$ be a large enough integer, and replace each tuple $(a_{i1},\ldots,a_{ik})$ with the single integer $\sum_j a_{ij} M^j$. You now have an equivalent instance of PARTITION. Your problem appears in the literature, under the name multidimensional two-way number partitioning, in Jelena Kojić, Integer ...

2

Depending on your intended use, it might not be practical to use counters, e.g. integers instead of bits, but by doing so, you can increment each integer in the array instead of setting a bit when inserting. When removing an element, you can then decrement all of its related integers.

2

If there would be a polynomial time algorithm for your problem, it could be used to solve the NP-hard recognition problem in polynomial time by just giving the input to it and checking if its output is correct. Therefore the problem you pose is NP-hard in the sense that if it admits polynomial time algorithm, then P=NP. (Here we assume that the input is some ...

2

One of the complications here is that there is no natural "decision variant" of this problem, since this isn't an optimization problem. (and the problem "given an UDG, is there a realization?" is trivial) Since reductions between decision problems tend to be better studied, one option is to make it an optimisation problem in a chosen ...

2

Broad context First off, the field in which this sort of research would be carried out is called computational social choice (theory). Searching for papers or books in that field will give you exactly what you ask for: literature on mathematical models of (political) voting schemes, and related topics like resource allocation and judgement aggregation. As ...

2

Categories can be used to model databases, and have been used for data integration. See also this paper. There's a pretty gentle introduction in chapter 3 of Seven Sketches in Compositionality. Coalgebras are a generalization of automata, and have provided insight into notions of bisimulation. I saw a talk about this, but also found this paper Closed ...

2

The "Algorithm 1 Pivot selection" of that paper is rather sloppy. The critical mistake is, as you have noted, "the while loop in the algorithm is exited too early due to the stride being reduced down to zero before the correct pivot element has been found". There are two other drawbacks. The condition, a[len(a) − pivot − 2] < b[pivot +...

2

Your theorem doesn't hold. Consider the grammar \begin{align} &S \to 1T \mid T1 \\ &T \to 23 \mid 32 \\ \end{align} Shuffling the grammar results in the same language. Now consider instead the grammar $$S \to 123 \mid 132 \mid 231 \mid 321$$ which generates the same language. Shuffling this grammar results in a larger language.

2

In modern papers, and unless stated otherwise, NP-hardness is one of the following: A decision problem is NP-hard if it is NP-hard with respect to many-one reductions. An optimization problem is NP-hard if its decision version is NP-hard. Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem ...

2

This is likely to be a challenging task, and if you're not familiar with image classification, I suspect it may be beyond what you can reasonably do right now. I would suggest you investigate classical image processing techniques. You might try applying morphological operators, such as closing (dilation followed by erosion) or opening followed by ...

1

The answer to your first question is: Not that we know of. A grammar is $\hbox{LALR}(k)$ if and only if its $\hbox{LALR}(k)$ automaton is deterministic. The only way that we know of checking that a grammar is $\hbox{LALR}(k)$ is to build the automaton, or something that essentially amounts to building the automaton. The good news is that the key complication ...

1

This idea is sufficiently well-known that I'm pretty sure I've seen papers just say things like "we can count the number of paths by dynamic programming" and stop there, with the expectation that the reader can fill in the details. It is also the semiring problem for $\mathbb{N}$ with the usual $+$ and $\times$, and can be extended to cyclic graphs ...

1

Not what you are hoping for, but: An early version of the OCaml language was based on the idea of a categorical abstract machine "represented by Cartesian closed category". Haskell's monad classes "are based on the monad construct in category theory".

1

A silly example: Checking if a graph has more than m nodes. :-) Some more interesting examples: Checking if a graph is connected. Checking if a graph has an Eulerian cycle. A graph is Eulerian iff all degrees are even and the graph is connected: https://en.wikipedia.org/wiki/Eulerian_path Checking if a graph has a perfect matching: https://en.wikipedia.org/...

1

Impossibility result #1: dropped events The problem cannot be solved in general; there is no way to guarantee that your requirements will be met if some events are dropped (i.e., not received). Consider first this stream: e1 = { name: Jhon, timestamp: 1 } e2 = { name: Jhon, timestamp: 4 } where the algorithm sees both events. Next, consider this stream: ...

1

The two most relevant rigorous results are: Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-SAT problem. This paper (with an appendix by Jean Bourgain) shows that $k$-SAT exhibits a sharp threshold. However, a priori this threshold could depend on $n$ (i.e., this method cannot show that $\alpha$ is constant). Jian Ding, Allan Sly, Nike Sun, ...

1

Based on this answer from Math.SE you can construct a simple algorithm for uniformly sampling an even spanning subgraph. Assume without loss of generality that $G$ is connected (otherwise you can apply the sampling algorithm to each connected component and return the union). Let us denote $G$'s vertices by $v_1,...,v_n$, and given $i>1$ let $P_i$ be some ...

1

I usually recommend An Introduction to Statistical Learning if you're starting out and Elements of Statistical Learning if you're a bit more advanced. They are both equally pleasing and completely free.

1

There is a survey by Luby and Wigderson: Pairwise independence and derandomization.

Only top voted, non community-wiki answers of a minimum length are eligible