# All Questions

10,517 questions
Filter by
Sorted by
Tagged with
4 views

### Shortest path on a hypergraph with no leftovers

In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by ...
40 views

### Understanding Dudley Chaining Argument for Rademacher Bound

I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know ...
164 views

### Complexity of constructing minimum depth decision trees

I am interested in the computational complexity of Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does ...
23 views

### Delaunay Triangulaition (or Voronoi) for a specific distribution of points

I found a paper about Delaunay triangulation for a set of points that are distributed by the Poisson distribution (https://pdfs.semanticscholar.org/9693/4b7e8e5483893f4874d7ba6afd812bbfe0ba.pdf). The ...
195 views

### About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives

What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective? Are there any necessary ...
41 views

### flip coin multiple times, see one head. then, how many tails in expectation? [closed]

Intuition says one, but my calculation by negative binomial distribution says two? I got very confused. Thank you!
52 views

### From Church-encoding to induction principle

I am looking for an algorithm to go from a Church-encoded datatype to their induction principle in the Calculus of Constructions. For example: ...
163k views

### What papers should everyone read?

This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different. We all have favorite papers in our own respective ...
65 views

### How Does Newton's Method Always Converge? [closed]

I've been working on some Stanford open courseware and right now I'm stuck on this homework problem. I was wondering if anyone could help. I can get everywhere before the horizontal pencil line but ...
20 views

### Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?

I have just started on the book Elements of Programming (2019) and after thinking about the definitions for value types in chapter 1, that in principle seem to link meaning (the abstract entities of a ...
8k views

### How is proving a context free language to be ambiguous undecidable?

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
36 views

### When can partial spectral sparsifiers be combined?

A few important papers about spectral sparsifiers and friends contain a technical idea that involves building many different sparsifiers that each "partially" solve the problem, and then combining ...
1k views

50 views

### Weakest condition that connects $P=BPP$ and derandomizing $VV$

It is known $P=BPP$ is insufficient to derandomize $VV$ isolation lemma. What does it mean to be 'insufficient' here? Is there some theorem which says $P=BPP$ $+$ 'condition $A$' gives ...
86 views

152 views

### Problem in deterministic time $n^p$ and not lower

I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable). ...
2k views

### Problems that can be used to show polynomial-time hardness results

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
254 views

### Infinite process balls in bins problem

Given $n$ balls and $m$ bins, let us consider an infinite process, where in each time slot we throw a ball at a random bin. When all $n$ balls are thrown, we take the balls from the bin with the ...
160 views

### Which types are nihilistic?

[Note 2020-02-08: I updated the definition of nihilistic types so that it relies less on the type Empty.] A discussion on Twitter prompted the following question, ...
21 views

### Applicability of M/D/1 queue for multi-class demand arrivals

Assume a queue system working as follows. Let $\lambda_i$ represent the Poisson demand rate for a customer class $i$ and $\mu$ represent the constant (deterministic) service rate. We have multiple ...
30 views

### Exponentiation: Function Problem that must take exponential time? [closed]

Introduction The powers of 2 seem to be a sparse language. Because every time I see a power of 2 expressed in a binary-string the amount of 0-bits is always equal to $X$ in $2^X$. For example, 10000 ...
26 views

### Complexity of solving systems of linear equations with hash preimages

Consider the following problem: Let $H$ be an arbitrary cryptographic hash function. The goal is to solve the following system of linear equations with integer coefficients \boldsymbol A \...
28 views

### What is the number of states in minimal dfa that accepts a bnary number divisible by 2 but not divisible by 3? [closed]

I am able to find out states in individual dfas but not after combining both. Can anybody solve this question please.
16 views

### Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
108 views

### Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
111 views

### Is this greedy algorithm for vertex cover studied before?

For the vertex cover problem (Given a graph $G$, find a minimum set $S$ of vertices such that $G - S$ is edgeless), there are two famous greedy algorithms. The edge greedy (finding an edge and taking ...
126 views

### Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?

Background It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$. Although some natural problems are known to exist, many of them ...
26 views

### Minimum rank graph cut

Consider the following problem: Input: A graph $G=(V,E)$ and a matroid $M$ on $E$, given by an independence oracle. Task: Find a cut $C\subseteq E$ in the graph, such that the rank of $C$ in the ...
16 views

### local tree-like structure of stochastic block model

For a stochastic block model $SBM(n, p, q)$, what conditions can we impose on $n, p$ and $q$ that for any given vertex $v$, the distance 2 neighborhood of $v$ would have tree-like structure?
33 views

### Family of functions with properties similar to k-wise independent hash functions

I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a ...
Consider the following game on a directed weighted graph $G$ with a chip at some node. All nodes of $G$ are marked by A or B. There are two players Alice and Bob. The goal of Alice (Bob) is to ...