## Top new questions this week:

### How to define a similarity between two graphs?

Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G_1 = (V, E_1)$, $G_2 = (V, E_2)$. $\newcommand\mG{\mathbb G}$(...

graphs graph-isomorphism

### Integral solutions to circulation problem

Suppose we have a circulation problem (with only one commodity), where all lower bounds, upper bounds, and costs are integers. Are we guaranteed that if there is a solution, then there is an integral ...

network-flow

### Min path cover for a three-layer graph with all paths traversing all layers

Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. ...

graphs combinatorics discrete-mathematics

### Sampling from specific random distribution on sets

I have a random distribution on sets in mind, that has three parameters: $n, w, k$. The goal is to sample sets of $k$ integers from $[0, n)$ (without replacement) such that the elements within each ...

randomness sampling

### What are the implications of Homotopy Type Theory?

I've recently come across the topic of homotopy type theory and I'm interested to learn more. I have a very limited background in type theory. Can anyone tell me, in functional programming terms or ...

type-theory functional-programming mathematical-foundations proof-assistants homotopy-type-theory

### Upper bounds for a binomial coefficient

I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k$...

algorithm-analysis runtime-analysis big-o-notation

### Annotated type system problem about conditional branch

I am reading the book "Principle of Program Analysis" by Flemming Nielson for annotated type systems. In the first chapter, section 1.6 they mentioned the simple type system for various ...

compilers type-inference

## Greatest hits from previous weeks:

### The math behind converting from any base to any base without going through base 10?

I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still ...

algorithms arithmetic number-formats

### Why are there so many programming languages?

I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with ...

programming-languages

### Is there a name for the class of algorithms that are the most efficient for a particular task?

This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps. We would ...

algorithms time-complexity terminology

### Why do more powerful programming languages tend to have slower implementations?

I was reading this article. The author talks about "The Blub Paradox". He says programming languages vary in power. That makes sense to me. For example, Python is more powerful than C/C++. ...

programming-languages

### Definition of the state of an object in OOP

I need a concise definition of the "state of an object" in object-oriented programming (for a paper). For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find ...

terminology reference-request programming-languages object-oriented

### What are the differences between computer vision and image processing?

What are the differences between computer vision and image processing? For example, in object recognition, what are the roles of computer vision and image processing?

terminology computer-vision image-processing education

After reading several sources I'm still confused about user- and kernel-level threads. In particular: Threads can exist at both the user level and the kernel level What is the difference between ...

operating-systems terminology concurrency os-kernel

## Can you answer these questions?

### Circuit complexity of hardest monotone function

Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such that the minimal size of a monotone circuit that computes $f$ is $\Omega(2^n / n^2)$. Use the fact that the number of ...

complexity-theory circuits boolean-algebra

### Automated algorithm design

There is a huge field of study dedicated to automated theorem proving. Is there any similar research dedicated to automated algorithm design? And is there any form of "duality" between these ...

logic
An edge-labelled directed graph is the data of $G = (V, E, l)$ where $(V, E)$ is a directed graph, and $l \colon E \to \mathbb{P}$ is some function. (For the graph I am considering, labels take values ...