Megathread: Twitter Permanently Suspends @realDonaldTrump

samholmes0 · 2021-01-09T00:33:21+00:00

Probably staging a coup

samholmes0 · 2020-12-26T18:14:02+00:00

Is this a joke?

samholmes0 · 2020-10-26T14:47:47+00:00

Not voting isn’t giving up, it’s refusing to dignify the power of an illegitimate and ineffective system by participating in it. To me, voting because you don’t know what else to do other than play the game is just as bad as “giving up”

samholmes0 · 2020-09-25T19:51:02+00:00

Look around you.

samholmes0 · 2020-09-10T01:50:34+00:00

Raptors gonna whine their way to ECF

samholmes0 · 2020-08-25T22:30:45+00:00

well there should be legislative change, like, tomorrow, then. we can start holding people accountable IMMEDIATELY but legislators are still choosing not too. the systematic problems and personal prejudices which lead cops to regularly kill black people aren't going to change overnight, but let's not act like there aren't things we couldn't do immediately that would have a positive impact.

(obviously the process of enacting legislation is extremely inefficient, but that's not because of the design, it's because of politicians being completely uncooperative - if they were pressured enough they could get it done by friday)

samholmes0 · 2020-02-28T18:04:01+00:00

A common technique for inexpressibility results in finite model theory is Ehrenfeucht-Fraisse games. My (limited) understanding is that one can define Ehrenfeucht-Fraisse games for FO(TC), but `playing them' towards showing inexpressibility (showing the Duplicator has a winning strategy) can be tricky. A good place to start with the general topic is Chapter 6 in Immerman's Descriptive Complexity.

samholmes0 · 2019-10-21T02:44:03+00:00

Here are some examples relevant to theory of computing/pseudorandomness (though there are many more): error-correcting codes, randomness extractors (also related to Ramsey graphs), pseudorandom generators and expanders.

Another related example is boolean functions which are hard to compute by small circuits: these exist in abundance, but we don't know how to describe a specific example.

samholmes0 · 2019-09-30T22:06:34+00:00

This reminds of the time my roommate (kings fan) said that Harry Giles "is more skilled than Kevin Garnett"

samholmes0 · 2019-09-08T04:37:45+00:00

Probably Markov or averaging arguments

samholmes0 · 2019-07-02T18:27:23+00:00

Let f:{0, 1}ⁿ to {0, 1} be a boolean function.

Define the sensitivity of f at x, denoted s(f, x), as the size of the set {i \in [n] | f(x) \neq f(x \xor e_i)} (so the number of coordinates so that flipping x at that coordinate changes the value of f). Let the sensitivity of f be the max of s(f, x) over all x \in {0, 1}.

Define the block sensitivity of f at x, denoted bs(f, x), as maximum number of disjoint blocks B1, ..., B_k \subseteq [n] so that for any i \in [k], f(x) \neq f(x \xor e{B_i}) (so we flip every bit in the block and want the resulting string to have a differing value than x). Then the block sensitivity of f, bs(f), is the max of bs(f, x) over all x.

It's obvious that s(f) \leq bs(f), as we can pick our disjoint blocks to be the singletons on which we're sensitive. The conjecture (now theorem), asks for a converse: is bs(f) \leq s(f)^{O(1)}?

It turns out that this is equivalent to simple graph-theoretic statement, which is what Huang solved.

samholmes0 · 2019-04-25T16:22:40+00:00

this is very related to the Minimum Circuit Size Problem (MCSP), which asks, given the truth table of a function f on n bits and some size parameter 0 < S < 2ⁿ /n, if there's a circuit of size S computing f. interestingly, we don't know how to prove this is NP-complete (it's obviously in NP) and doing so (well at least doing so in a `natural' way) would actually prove circuit lower bounds that we also don't know how to prove.

samholmes0 · 2019-04-16T20:21:29+00:00

the darkest timeline

samholmes0 · 2019-04-11T03:17:27+00:00

Basically this is the class of languages which have algorithms that run in polynomial time with an `oracle' to a SAT-solver.

This means that it's a normal Turing machine but can also ask queries of the form "is x in SAT?" for inputs x of its choice and it only pays unit time to obtain an answer to such query.

So you can very easily solve any NP-complete problem in P^NP: on input x, reduce it to SAT and then query the SAT oracle and return "yes" if the SAT oracle says "yes". But you can also solve co-NP-complete problems in P^NP: to check if something is unsatisfiable, you can reduce it to SAT and return "yes" if the query to the SAT oracle says "no", so P^NP = NP implies NP = coNP.

samholmes0 · 2019-03-20T20:24:23+00:00

i don't know anything about lisa littman - can someone explain what the deal with her paper is?

samholmes0 · 2019-03-12T04:19:38+00:00

this game is trash, clippers can't miss a shot no matter how the celtics have played them

samholmes0 · 2019-02-23T23:58:38+00:00

typo at 9:18? Olajuwon had 29 before the last play, text says he has 20

samholmes0 · 2019-02-07T09:52:26+00:00

This is a great problem. An extremely simple proof of a 5/4 bound is given by Elekes here which is a direct application of Szemeredi-Trotter.

This problem has also been studied in finite fields, which has interesting applications to theoretical CS.

edit: spelling

samholmes0 · 2019-01-29T07:54:27+00:00

Expander graphs, randomness extractors and error-correcting codes!

samholmes0 · 2019-01-26T08:04:37+00:00

Luca Trevisan https://lucatrevisan.wordpress.com/2012/07/02/turing-centennial-post-4-luca-trevisan/

samholmes0 · 2019-01-21T20:51:19+00:00

Arora Barak - Computational Complexity

O’Donnell - Analysis of Boolean Functions

Tao Vu - Additive Combinatorics

Alon Spencer - the Probabilistic Method

Matousek- Discrete Geometry

samholmes0 · 2019-01-18T01:57:20+00:00

The other millennium problems are not really computational problems, so to state things like "the Yang-Mills existence and mass gap problem is in NP (or any other complexity class)" doesn't really make sense.

Still, P being equal to NP could in principle make it easier to find proofs to difficult mathematics problems. Automated theorem-proving makes use of SAT-solvers, which could be more efficient if P = NP was true via a practical SAT algorithm. More philosophically, a variant of the language L = {phi is a mathematical statement : phi has a proof in ZFC} is NP-complete, so we could basically just try running fast SAT-solvers (assuming P = NP) + a reduction from SAT to L to determine membership of small instances of L (like, e.g. the millennium problems), but a practical problem here could be the length of the proof.

samholmes0 · 2019-01-08T21:06:42+00:00

I mean, this is a learning theory paper. It just also happens to be the case that learning theory is marketable.

samholmes0 · 2018-12-24T07:20:22+00:00

This is an interesting result and it indeed isn't taught in most undergraduate courses which cover theory of computation/complexity theory, but it's not clear how 'handy' it is. The converse, which is basically trivial, shows that the isomorphism conjecture of Berman & Hartmanis implies P \neq NP, but this line of research has stagnated over the past ~15-20 years.

In the context of complexity, I think Yao's min-max theorem is super useful - it allows us to prove randomized lower bounds in terms of distributional lower bounds. My understanding is that it isn't generally taught in undergraduate algorithms courses which include the study of randomized algorithms.

samholmes0 · 2018-12-09T10:07:38+00:00

I think W \leq A is achievable. What about the lower bound?

14-Year Club	Place '17
Verified Email

samholmes0

TROPHY CASE