# All Questions

11,646 questions
Filter by
Sorted by
Tagged with
143 views

### What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)

Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\mathbb R^+$, and an integer parameter $k\in\mathbb N$. The Entropy-Constrained Quantization problem asks what is the best ...
237 views

### Does such a graph exist? [closed]

[EDITED FOR CLARITY] Does there exist an edge-colored graph $G$ with the following properties? $G$ has a vertex $r$ with exactly three, distinctly colored, incident edges: $(r, u)$, $(r, v)$, $(r, w)$...
224 views

### Type theory and fixed points of datatypes

For the purposes of this question, say that a datatype is a type constructor with one type parameter (this is sometimes called a type operator). In Haskell, we can define a fixed point ...
80 views

### Implementation of vectors as dependent types in CoC

I'm trying to understand dependent types in CoC and I am having trouble finding examples that are actually carried out in CoC, specifically without inductive types or pattern matching. The most ...
105 views

### A counter example for the set mean objective

Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function \begin{align} cost(\mathcal{P},c) =...
278 views

### Complexity of optimal elimination for a planar tensor network

Edit Dec 15 it's not obvious this problem is tractable when further restricting to trees, see cs.SE question Suppose we need to sum out variables in a tensor network (a factor graph where each ...
54 views

### Worst to average case reductions for quantum complexity classes

I am studying worst to average case reductions for different complexity classes. Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...
61 views

### Properties of the polymorphic type $\Pi t : * . ((t \to t) \to t) \to t$

In the context of pure type systems (say Calculus of Constructions) I am looking for references discussing the properties of the following polymorphic type: $\Pi t : * . ((t \to t) \to t) \to t$. What ...
64 views

### What are some examples of non-algebraic effects?

In this (the only at time of writing) answer to How to tell if an effect is algebraic? informative positive examples are given. But I suppose that's less complete without negative examples, to ...
239 views

### When should one start looking at existing results in theoretical CS?

I'm currently a PhD student in theoretical computer science. I've been working on this problem daily for almost a month that has been well studied and was assigned to me by my advisor. The problem is ...
122 views

### What is wrong with the "obvious" approach to function extensionality by providing context-aware rewrites?

There is an obvious, dirty and probably wrong approach that allows one to prove function extensionality in a straight-forward manner: provide an equality primitive with a context-aware rewrite. For ...
102 views

### Algorithm for finding traffic equilibrium

I watched a youtube video about a certain interesting property of springs and road networks. It made me think: if we represent a network of roads as a graph where edges are roads described by a ...
290 views

### Which universities in the U.S. are doing research in type theory?

The question is meant to be broad in that recommendations with mentions of the particular areas within type theory research are greatly appreciated. Also, the research need not be conducted in ...
116 views

### Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

It is mentioned in multiple papers [1], [2] that $MODp \circ MODq$ circuits for two distinct primes $p, q$ can compute arbitrary functions in exponential size. However, [1] provides no citation for ...
116 views

### Parameterized complexity of tree/branch decomposition

I'm looking for an up to date reference for parameterized complexity of tree and branch decompositions. IE, complexity of finding tree/branch decomposition of optimal width in terms of relevant graph ...
109 views

90 views

### Complexity of merging two convex hulls in $\mathbb{R}^d$

Given two convex hulls $C_1, C_2$ in $\mathbb{R}^2$ or $\mathbb{R}^3$, it is known how to merge the two convex hulls into a a third convex hull $C$ (the convex hull of the points in $C_1, C_2$) in ...
1k views

### Full names of C. K. Chow and C. N. Liu

Where can I find the full names of C. K. Chow and C. N. Liu, of the Chow-Liu tree fame? https://en.wikipedia.org/wiki/Chow%E2%80%93Liu_tree https://ieeexplore.ieee.org/document/1054142
131 views

### How to read a COLT or other paper related learning theory?

I am a master student right now. And first time met the theoretical computer science, I am really interested in it, and especially the learning theory part. Wish to do research about this part in the ...
173 views

### Is there a precise definition for big O notation with 2 or more variables [closed]

Big O notation has a very precise definition for 1 variable. You can prove O(2x^2) = O(x^2) for example. There is never ambiguity. However, for 2 or more variables ...
26 views

### Can we pick a basis for synchronous circuits which coarsens towards the target partition at every layer?

Given a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ and a Boolean basis for circuit gates $B$ (for instance $B = \{AND, OR\}$), we can construct the set of size optimal synchronous (Harper ...
94 views

### Do random functions have synchronous, alternating circuits with non-injective first layers?

After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a ...
132 views

### Reference request for linear algebra over GF(2)

I have been looking for materials on the linear algebra over $GF(2)$ but so far I haven't found any substantial textbooks or notes on this subject. In fact in one of the notes I found the introduction ...
197 views

54 views

### Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?

Let $G$ be a simple undirected plane 4-regular graph. Basic definitions are given at the bottom of this question. An Eulerian orientation of $G$ is good if for each vertex $v$ of $G$, the edges around ...
151 views

### "Looking for help understanding a proof by Gossner (1998)."

Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
197 views

### Does abundance of max cliques make it easy to solve COLORABILITY?

Let $q\geq 3$. We know that $q$-COLORABILITY is an NP-complete problem. Suppose that $G$ is a graph such that each vertex of $G$ is part of a $q$-clique (i.e. $K_q$). Since we may assume that $G$ does ...
140 views

### Q: Trusting program output from an untrusted machine

Let's suppose that we create a program P, that given input I, generates output O. We then want to run this program on an untrusted computer C that may either want to tamper with the program (run P' ...
176 views

### Young Diagrams and distinguishing between two distributions

Introduction: The reference for everything is this paper. The Robinson–Schensted–Knuth (RSK) algorithm is a well-known combinatorial algorithm with diverse applications throughout mathematics, ...
52 views

### Algorithmic game theory with decentralized mechanism of exchanging information

An intresting topic that I want to understad has to do with the decentralized exchange of information among a network of agents, however there is not a specific theory to make such a mathematical ...
234 views

### How can we compute the VC dimension of a finite class of sets?

Let $F$ be a class of subsets of a finite set $X$ of cardinality $n$. What is the complexity of computing the VC dimension of $F$? Can we do better than looping through every subset of $X$ and ...
59 views

130 views

### Finding a path in a graph hitting a particular vertex

Problem: Given three vertices $u, v$ and $w$ from an undirected graph. Find a path (where vertices are not repeated) from $u$ to $w$ that passes through $v$. This problem has been mentioned in ...
81 views

### Query about P/poly and Polynomial Hierarchy Collapse to $\Sigma _{2}$

I am not conversant in the complexity class $P/poly$. While reading about the class on wiki I encountered two conditional statements about it, namely: If $NP ⊆ P/poly$ then $PH$ (the polynomial ...
### Bin packing where each item must occur in $k$ bins
I am looking for information on a generalization of bin-packing in which each item should appear in exactly $k$ different bins, for some positive integer $k$. The standard bin packing problem ...