Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
Yury's user avatar
Yury's user avatar
Yury's user avatar
Yury
  • Member for 11 years, 10 months
  • Last seen this week
35 votes

Why did Kolmogorov publish Karatsuba's algorithm?

22 votes
Accepted

Balls and Bins analysis in the $m \gg n$ regime: gaps

20 votes

Reference for NP-hardness of 3-colouring?

19 votes

Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?

17 votes
Accepted

Robustness of splitting a junta

15 votes
Accepted

An extension of the noise operator

15 votes
Accepted

Another variant of PARTITION

14 votes
Accepted

Using Kolmogorov complexity as input "size"

14 votes
Accepted

Is the following graph optimization problem approximable within a constant factor?

14 votes
Accepted

Trying understand a move in Cohen's proof of the independence of the continuum hypothesis

14 votes
Accepted

A question on linear extensions of partial orders

12 votes
Accepted

Optimal NP solvers

11 votes

Approximation algorithms for Directed Minimum Cut with Cardinality Constraints

11 votes

Smallest set not included in a collection of sets

11 votes
Accepted

What bound can we get using $k$-th moment inequality under 3-wise independence?

11 votes
Accepted

Sum of products of all combinations?

10 votes
Accepted

What is the connection between moments of Gaussians and perfect matchings of graphs?

9 votes

Inappoximability status of Max One in Three SAT for satisfiable instances

8 votes

What is the best-known inapproximability result for MIN-3CNF-DELETION?

8 votes

What are the hardness results known for CSP over $\mathbb{F}_q$?

7 votes
Accepted

Statistical distance between uniform and biased coin

7 votes
Accepted

Small graph with gap between chromatic and vector chromatic number?

7 votes
Accepted

Minimizing the maximum dot product among k unit vectors in an n-dimensional space

7 votes
Accepted

Is it in NP to check if the convex hull contains the unit ball?

6 votes

putting objects in buckets -- optimization problem

5 votes

Approximability of the genus problem

5 votes

Partition of $\{(i, j)\ |\ i \neq j \leq n\}$

4 votes

How to iterate over vectors in order of probability in small space

4 votes
Accepted

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

4 votes
Accepted

A weighted sorting problem