17 votes

Math talk: Theorem about git revision control system?

Interestingly, there is a nascent mathematisation of version control systems, although at this point it's only partially applicable to Git. It's called patch theory [1, 2, 3, 4, 5] and arose in the ...
user avatar
16 votes
Accepted

Math talk: Theorem about git revision control system?

A git repository can be thought of as a partially ordered set of revisions (where one revision is earlier than another in the order if it is a direct or indirect successor of the earlier one). The ...
user avatar
16 votes
Accepted

Can theoretical computer science be applied in social sciences?

I won't say it is impossible, but to me it seems... challenging at best. Social science deals with the behavior of humans, and humans are complex. TCS deals with mathematics and computer algorithms, ...
user avatar
  • 10.4k
12 votes

Can theoretical computer science be applied in social sciences?

There are some interdisciplinary areas in CS that may be similar to what you're looking for. These areas are often considered "applied", in the sense that they restrict their research to a ...
user avatar
11 votes

Can theoretical computer science be applied in social sciences?

Yes, absolutely! This is a blossoming new field in the social sciences that a lot of people are excited about right now. The phrase to look for is "computational social science". There is ...
user avatar
  • 119
9 votes
Accepted

Are social networks typically good expanders?

Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap. What you could hope for is good ...
user avatar
8 votes

Applications of Hamiltonian Cycle Problem

One application involves stripification of triangle meshes in computer graphics — a Hamiltonian path through the dual graph of the mesh (a graph with a vertex per triangle and an edge when two ...
user avatar
8 votes
Accepted

any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

There are lots of overlaps between small world and scale-free, but I think much less so between those two and expanders. The terms "small world" and "scale-free" are often used informally, but formal ...
user avatar
8 votes

TCS oriented refs/survey on group theoretic word problem

One family of results not mentioned in the excellent references of @Marzio's answer is relations between the isoperimetric (Dehn) function of a group $G$ and the nondeterministic time complexity of ...
user avatar
7 votes
Accepted

TCS oriented refs/survey on group theoretic word problem

I think that you can start (and probably end, because it's a huge list :-) with the references in the recent Charles F. Miller's paper: "Turing machines to word problems" (2013). And another recent ...
user avatar
7 votes

Applications of Hamiltonian Cycle Problem

I think there are some applications in electronic circuit design/construction; for example Yi-Ming Wang, Shi-Hao Chen, Mango C. -T. Chao. An Efficient Hamiltonian-cycle power-switch routing for MTCMOS ...
user avatar
6 votes

Can theoretical computer science be applied in social sciences?

It seems to me that your best chance at applying TCS to social sciences is to apply it to study problems in economics. In particular, one can use TCS to argue that certain tasks required in economics ...
user avatar
5 votes

Are any of the state of the art Maximum Flow algorithms practical?

You might be interested in Maximum Flows by Incremental Breadth-First Search by Goldberg, Hed, Kaplan, Tarjan, and Werneck http://research.microsoft.com/pubs/150437/ibfs-proc.pdf http://www.cs.tau.ac....
user avatar
5 votes

Applications of Hamiltonian Cycle Problem

(Variants of the) TSP show(s) up routinely in several routing and scheduling problems (think of the route planned for a UPS truck out of delivering packages, for instance). But a great place to learn ...
user avatar
  • 316
4 votes

Math talk: Theorem about git revision control system?

Another alternative is to look at persistent (or purely functional) data structures. Git's internal data structure can be seen as a confluently persistent tree: a persistent data structure is a ...
user avatar
  • 243
2 votes

Ecology and evolution through the algorithmic lens

heres a new notable paper linking evolution/genetics to the Multiplicative Weight Update algorithm, also just profiled by the Simons foundation & includes a coauthor cited in the question (...
user avatar
  • 10.8k
2 votes
Accepted

what can be said about complexity of "typical" supercomputing programs/ applications? any NP hard?

The manufacturers of the computing hardware themselves are their own customers, and use supercomputing to approximatively solve a number of well-know and more obscure NP-hard tasks. One of the oldest ...
user avatar
2 votes

Can theoretical computer science be applied in social sciences?

I used to study economics, and the answer is yes. In 2019/2020 Nobel Laureate Paul Milgrom gave the marshall lectures in cambridge with the title "Market Design When Resource Allocation is NP-...
user avatar
1 vote

Can theoretical computer science be applied in social sciences?

"Stupid" is subjective and judgmental, but there are certainly meaningless, trivial, or uninteresting questions. Or at least sometimes they can seem meaningless until someone comes along and ...
user avatar
  • 10k
1 vote

Are social networks typically good expanders?

Power-law graphs are arguably good models for social network graphs. This paper by Gkantsidis, Mihail, and Saberi shows that power-law graphs are expanders.
user avatar
  • 1,120
1 vote

Math talk: Theorem about git revision control system?

Yes, you can mathematically define how Git works. You could define primitive Git structures and Git operations on them and then have theorems that prove that using these operations in particular ways ...
user avatar
1 vote

How to map random cardesian points in a 2d array

This is impossible in general. The reason is that the grid-distance is symmetric while being closest neighbors is not a symmetric relation. If you have many points ($\geq 9$) close to the origin and ...
user avatar
  • 9,378
1 vote

What are some real world applications for genetic algorithms?

The annual GECCO conference (pretty much the premier venue for evolutionary computation research) has a `Real World Applications' track. See also this recent presentation:
user avatar
1 vote

How can I prove that Hamming distance is upper bound for Levenshtein distance?

To add on Andrej's answer, consider two strings "1234567890" and "0123456789". Attempt to convert one into the other. One takes 2 operations (namely, insert and delete) and the other takes 10 (...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible