skyspace3.0 thoughts
[06-21-24]
I am still not sure how / to what extent I want to move from skyspace2.0 to skyspace3.0 (/personal wiki/ whatever the other site is). Do you have thoughts?
[06-21-24]
I am still not sure how / to what extent I want to move from skyspace2.0 to skyspace3.0 (/personal wiki/ whatever the other site is). Do you have thoughts?
[05-20-24]
Suppose you had a function that was a direct product. Could you tell? Yup.
[05-14-24]
I write some notes about an article by Markus Bläser, Balagopal Komarath, Karteek Sreenivasaiah on detecting induced cycles and paths in graphs.
[05-12-24]
This story should hopefully be somewhat recognizable as a (heavy) revision of the previous short story 1, which was titled "short story 1". I think it works better, but this might be a controversial take. In any case, hope you enjoy.
[05-01-24]
I'm too busy to write a proper post atm. But have been seeing some really neat things in classes, breifly jotting a note to self about them.
[04-23-24]
In this post I will give a proof of Dirichlet's Theorem: in any (reasonable) infinite arithmetic progression there are infinitely many primes. Actually we will probably get a nice density statement that is stronger than this.
[04-15-24]
For my stochastic processes final project I'm reading a paper about understanding the solution geometry of random coloring instances. The paper is: Dimitris Achlioptas, and Amin Coja-Oghlan. "Algorithmic barriers from phase transitions." 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2008. I think it's quite neat. In this post I will organize some thoughts that I had after reading the proof sketches.
[04-14-24]
This story is still on alpha release. Feedback appreciated.
[04-09-24]
Modular forms sound freaking fancy. This post defines the modular group and describes its action on the upper half complex plane. It's actually a really simple group, it's generated by two really simple transformations. It makes some really nice pictures. Anyways this post should be really chill it's just some basic geometric facts. I think it's kind of cute though.
[04-07-24]
The circle method is a quite cool technique in analytic NT. Here is an exposition of the circle method for solving the Warring problem. Much of the analysis follows closely to Nathanson's book on classical additive bases, although in a few places I have tried to give simpler proofs of some of the statements, or otherwise deviated from his presentation to hopefully add clarity and motivation.
[03-06-24]
A major topic in additive number theory is the following question: given a set $A\subseteq \N$, can every sufficiently large positive integer be expressed as the sum of a bounded number of elements of $A$? If so, in how many ways can number $n$ be represented. We say that the set $A$ is an **additive basis** of order $h$ if every positive integer can be written as the sum of at most $h$ elements from $A$.
[02-28-24]
Two of the things that sound the coolest in Analytic Number theory are the circle method and sieves, e.g., selberg sieve and large sieve. I'm slowly learning about these. Here are some preliminary things I've learned.
[02-25-24]
Wrote this story for my class "writing short stories". Per popular demand posting this story here. No warranty.
[02-25-24]
I reread a few lecture notes from virginia's graph algo class specifically focussing on ones that seemed vaguely related to APSP.
[02-23-24]
summary of a paper which I believe is basically SotA for APSP approx.
[02-22-24]
Concentration inequalities are super useful. I write some down that I've heard lately so that they don't leak out of my brain. Or rather, so that they leak more slowly and so that hopefully by the time I realize I'm starting to forget I have an easy reference. Or maybe they will be so frequently useful that I won't have time to forget, unclear. Anyways, writing them down will increase Pr I remember to use them.
[02-22-24]
I've found a cool set of lecture notes from Harvard that talks about analytic number theory. In this post I give some of the basic ideas presented in the first couple notes.
[02-22-24]
This is a stub. I will *expand* it later. I'm serious pun aside. I really didn't have time to write it all down yet.
[02-21-24]
Jacob Foxs gave a nice talk about subset sums today. I summarize what I remember from it.
[02-15-24]
I explore a remark that was made today in Dor Minzer's class on analysis of boolean functions.
[02-07-24]
I write down some initial impressions / reactions to my classes this semester.
[01-21-24]
I feel like this title would be too dramatic if I didn't include a description blurb.
[01-14-24]
I realized that I have very few blog posts with the tag "approximation algorithms". Seeing as I had recently heard this algorithm for APSP approx I thought I'd write it down.
[01-08-24]
I read chapter 2 of the FPT book in a bit more detail. And try some more problems.
[12-26-23]
Proof from Appendix of Aboud FOCS22. "Hardness of approximation in P via short-cycle removal"
[12-26-23]
I was reading a couple of Virginia's https://people.csail.mit.edu/virgi/6.s078/ fine-grained complexity theory notes. Here I write down some of the cool things I learned while reading the notes.
[12-25-23]
In this blog post I summarize "Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics" by Abboud Bringmann and Fischer and also discuss the very similar "Removing Additive Structure in 3sum based reductions" by Jin and Xu.
[12-25-23]
I wanted to tell my sister about the KST theorem, so I'm writing it down here really fast first to make sure I understand it.
[12-23-23]
In this post I discuss the state of the skyspace software, some musings about software development, and of course a description of the newest feature of skyspace: encryption.
[12-19-23]
One of the most basic facts of linear algebra is that whenever you have $n+1$ vectors in an $n$-dimensional vectors space, there must be one of your vectors which can be expressed as a linear combination of the other vectors. This seemingly simple fact can prove some really interesting combinatorial statements.
[12-18-23]
In which I write down as many types of MM that I can look up, in hopes that they will help solve a **really** hard problem.
[12-14-23]
I write down some of the key problems, results, and ideas in the land of MM + graph algorithms.
[12-13-23]
Saw a cool complexity theory idea today. Quickly jotting it down so I don't forget it.
[12-13-23]
I feel like I can never remember what min-cost circulation (MCC) is, or what the basic facts about it are. So here is a short blog post where I remind myself of what MCC is.
[12-12-23]
The Beck Fiala theorem is a fundamental result in discrepancy theory. Basically it says, if you have a collection of subsets of a universe and each element of the universe shows up in a limited number of the sets in your collection then there is a 2-coloring of the universe such that all sets have a roughly equal number of red and blue elements.
[12-10-23]
Third philosophy essay, this time about a moral dilemma. THE PHILOSOPHY ESSAY IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE PHILOSOPHY OR THE USE OR OTHER DEALINGS IN THE PHILOSOPHY.
[11-24-23]
I skimmed a couple of lecture notes and textbooks about sketching. In this blog post I summarize some of the main takeaways.
[11-24-23]
Sometimes problems are hard. But sometimes they're less hard if you parameterize them correctly.
[11-11-23]
Skyspace2.0 has now existed for 1 year. What has it meant? I offer some analysis of skyspace2.0 and discuss my favorite posts.
[11-06-23]
Is it ethical to spend money on personal luxuries or things you find meaningful and important when this money could be repurposed to promote health and even save lives? I'm not totally sure, but must decide anyways. Alas, such is life. Anyways I wrote an essay about the question for my philosophy class, and by popular demand am posting it here. Interested to hear people's opinions, to what extent you disagree or agree, or if you have any other interesting arguments.
[10-09-23]
Selling and buying, how hard could it be? I'm not going to lie, it could be pretty simple.
[10-01-23]
today I spent way too long searching for a bunch of common bounds that are useful in, e.g., randomized algorithm analysis. Here are the bounds I found, a gift to a future myself.
[09-23-23]
We talked about a lot of special cases of SAT that are NP-hard in Erik Demaine's Fun with Hardness class. I have had a hard time keeping track of them all so I've created this little condensed reference for all the various versions.
[08-31-23]
The lambert-W function $x\mapsto xe^{x}$ turns up surprisingly often. For some reason I always have had a hard time approximating it. Today I finally found the "inequalities" section of the wikipedia page for Lambert-W function, and will share it here.
[08-27-23]
I give some stream-of-consciousness musings on choice, and then hopefully edit it into something readable and meaningful that has a point.
[08-25-23]
The fact \sum 1/n^2 = \pi^2/6 is well known and celebrated. In this note we present the simple fourier-analytic proof of this fact.
[08-03-23]
More than $1-\frac{1}{n}$ of the circumference of a circle is colored black. Can you draw a regular $n$-gon on the circle with all vertices in black regions?
[07-29-23]
In any finite coloring of $\Z^2$ there is a monochromatic axis aligned rectangle.
[07-26-23]
In the k-server problem you have k "servers" located in some topological space. You recieve a series of "requests", which are points in the topological space. You must respond to the request by moving some subset of your servers so that at least one server goes to the request. We will consider this problem in a metric space. You objective is to minimize the total distance travelled by all your servers. More precisely, our objective is to create a strategy that achieves bounded competitive ratio. We consider this problem with k=2 and set on a circle, where distance is measured along the circle.
[07-23-23]
The $k$-Farey numbers are reduced fractions of denominator at most $k$. They have several very interesting properties and are super useful. We investigate some of these properties.
[07-15-23]
Imagnie I have a postgres database with ~3000 columns storing boolean "flags" for ~1 billion rows. The "on" flag (1) is quite sparse, say occuring less than 0.1% of the time in each column. Now, I want to execute a query of the form "select all rows with flags 1,2, 5 and 101" 1. How much space would it take to store such a database? That is, will postgres by default do any sort of compression because of how sparse the "on" flag is? 2. Does postgres by default make queries of this form "fast"? If not, are there well known postgres extensions for this type of query? If not I might write my own, but just want to know if this has already been done.
[07-12-23]
Again #probfromthebook, this time discussing the classes of primes congruent to $1,3 \mod 4$.
[07-10-23]
Again #probfromthebook, this time discussing the infinitude of some classes of primes.
[06-25-23]
This is part of my series of doing problems from the book "problems from the book" (by Titu Adnreescu Gabriel Dospinescu). Today is about an interesting variant of Cauchy Schwarz.
[06-24-23]
This blog post is a bunch of very half baked thoughts / attempts at proving a certain number theoretical conjecture of mine that arose in the study of the maxload of a linear hashing variant with n objects to 2 bins.
[05-29-23]
Let $f_a(x)$ denote a binary string consisting of $a$ $0$'s followed by $a$ $1$'s and then repeating these $2a$ symbols. We can equivalently describe $f_a$ as $f_a(x)= \floor{x/a}\bmod 2$. We study $\sum_{x\in [ab]} f_a(x)\oplus f_b(x)$, in particular bounding the difference of the sum from $\frac{ab}{2}$.
[05-23-23]
A common question in extremal graph theory is "what conditions do I have to put on my graph to get property X" In this blog post, we investigate the question: how many edges to guarantee hamiltonian-cycle?
[04-13-23]
LCA and RMQ are some pretty fundamental problems. Can we solve in constant time with linear preprocessing? yes.
[04-06-23]
A hint of duality between chains and anti-chains in posets.
[03-29-23]
Numbers are so wierd! I don't get it, how are they so werid? here are some pictures showing their structured unstructuredness.
[03-25-23]
SCC are super cool and super useful. but how to compute them?
[03-12-23]
Have you ever wondered what binomial coefficients look like $\mod p$? turns out there is actually a simple answer. Credit to Enumerative Combinatorics for the problem
[03-06-23]
how dense can a numbers factors be? and how dense are primes?
[02-28-23]
finding a monochromatic arithmetic progression in a coloring of some numbers. And playing tick tack toe in high dimensions.
[02-17-23]
a better definition of the trace of a linear operator (which some people like to draw as matrices relative to arbitrary bases, sad)
[02-16-23]
Ever wondered what a semi-direct group product is? what, if anything is the difference between an inner semidirect product and an outer semidirect product? Yeah. I've wondered these things too. But then I met $\Z_5 \rtimes \Z_4$. And it became less mysterious.
[01-23-23]
Analysis of a couple of variants of a novel scheduling problem proposed by Nathan.
[01-19-23]
Binomial coefficients come up all over the place in combinatorics. This article gives a decent bound on the sum of a prefix of binomial coefficients. The bound get's pretty tight for like $(.1n, .5n)$, but if you can find something tighter, please let me know!
[12-21-22]
this is a lower bound for a research problem that I've been thinking about (a lot!) recently. And some reflections on what it means.
[tsp]
Travelling Salesman Problem (TSP) is one of the most famous NP-hard problems. Today, we are going to solve it really fast! (well, really just approximate it to within a factor of 1.5, but still).
[robot_panda_gardener]
I read a cool paper [Bilò, Davide, et al. “Cutting Bamboo Down to Size.” arXiv preprint arXiv:2005.00168 (2020)](https://arxiv.org/abs/2005.00168) and wrote a little "summary" of it. | very chill and very awesome!
[probabilistic_method]
I am going to try to read "The Probablistic Method" by Noga Alon and Joel H. Spencer. The Probablistic Method, pioneered by Erdos, is a really interesting way to think about combinatorics problems. Here is a high level overview of how proofs by the probabilistic method go
[measure_theory]
Read this if you are interested in any of the following questions: "what is a meausre space?", "what's a set in R that has no well defined inner-measure?" / why do measure spaces need sigma-Algebra's defined on them?", "what's a Lesbegue integral?", "what's Lesbegue's dominated convergence theorem?" (note: work in progress)
[functional_analysis]
Build up to, and proof of Projection Theorem. Might also talk about general Banach spaces but probably mostly Hilbert spaces.
