Theoretical Computer Science
Yuval Filmus's user avatar
Yuval Filmus's user avatar
Yuval Filmus's user avatar
Yuval Filmus
  • Member for 13 years, 1 month
  • Last seen more than a month ago
Profile Activity

156 Answers

Score Activity Newest
32 votes
Accepted

Is $AC^0/poly \cap NP$ contained in $P$?

30 votes

Representing OR with polynomials

29 votes
Accepted

Reasons for which a graph may be not $k$ colorable?

20 votes

The cozy neighborhoods of "P" and of "NP-hard"

19 votes
Accepted

Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?

19 votes
Accepted

A special class of languages: “circular” languages. Is it known?

19 votes

Graph theoretic restriction to Proofs in Proof Complexity Theory

18 votes
Accepted

Who introduced the complexity class AC?

17 votes
Accepted

What is worst case complexity of number field sieve?

16 votes
Accepted

The Cost of an Equivalence Query for DFA

15 votes
Accepted

Was bombe machine turing complete?

15 votes

finding smallest k elements in array in O(k)

14 votes
Accepted

Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

14 votes
Accepted

Anti-chromatic number

14 votes
Accepted

Rabin's "degree of difficulty of computing a function, and a partial ordering of recursive sets"

13 votes

Applications of $p$-adic numbers in CS

13 votes

Sensitivity-Block sensitivity conjecture - Implications

13 votes

Why does randomness have stronger effect on reductions than on algorithms?

13 votes

Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$

13 votes
Accepted

Smallest known formula for the determinant

13 votes

Post Correspondence Problem variant

13 votes

Do there exists polynomial size CFG that describe this finite language?

13 votes

Results in Theoretical CS independent of ZFC

13 votes

Polynomial-time algorithms with huge exponent/constant

13 votes
Accepted

Lower bounds on the size of CFGs for specific finite languages

13 votes

The computational complexity of matrix multiplication

13 votes
Accepted

questions on implications Babais quasi P time graph isomorphism result

13 votes
Accepted

Power of randomness vs. power of indefinite computation

12 votes

Efficient universal problem solver?

12 votes

What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

1
2 3 4 5 6

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.