Questions tagged [soft-question]

A soft question is a question (possibly subjective) about the field of theoretical computer science as opposed to being a question in theoretical computer science.

48 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
17 votes
0 answers
872 views

Deeper look at Algorithmica?

Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995. He presented five possible worlds we could be living in, depending on how P and NP were related. The ...
user avatar
14 votes
0 answers
443 views

Manuel Blum's supervisory style

Manuel Blum is a well-known theoretical computer scientist and a Turing award winner. But more interestingly, he has the highest number of students who have gone on to win a Turing award (Leonard ...
user avatar
  • 3,993
14 votes
0 answers
286 views

First use of sans serif for complexity classes

(Apologies for the triviality of this question; nevertheless, it's been bugging me and presumably people here will be able to answer it...) It seems that it has become popular in recent years to ...
user avatar
13 votes
0 answers
400 views

What percentage of SODA papers are galactic algorithms?

Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. ...
user avatar
  • 1,432
12 votes
0 answers
475 views

Looking for a quotation by Edsger Dijkstra

In one of his papers Edgser Dijkstra makes a statement like: "What we consider to be the standard case is one case among many exceptional cases only it occurs more often " or something along such ...
user avatar
10 votes
0 answers
228 views

Relatively low ambitious frontiers

What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing? For example: In the draft version of Arora ...
user avatar
  • 1,476
8 votes
0 answers
145 views

How to succeed in remote TCS research as undergraduate

I am participating in a remote summer research program in theoretical computer science due to the current pandemic. I recognize that given the current situation, it may be harder to collaborate with ...
user avatar
  • 81
8 votes
0 answers
667 views

Why is single authorship so common among breakthrough papers in computer science?

Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo ...
user avatar
7 votes
0 answers
184 views

Tortoise and hare algorithms

Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$. This problem has a stunning solution running ...
user avatar
7 votes
0 answers
230 views

Low barrier to entry Computational Complexity problems

I could use some help navigating which areas of Computational Complexity (e.g. CCC, STOC topics) require the least amount of background knowledge to get involved in basic research. I am looking to ...
user avatar
  • 395
7 votes
0 answers
317 views

Awards, grants and fellowships for PhD students in TCS

I think that a PhD student that received some awards and fellowships has better chance to get a good postdoc position. I was wondering what awards/grants/fellowships should one consider to apply for? ...
user avatar
7 votes
0 answers
548 views

Does a depth knowledge on theory of computation helps to be a better practitioner

I would like to know whether knowledge of the theory of computation can help you to be a better practitioner. Is it enough to obtain some depth of knowledge of algorithms and data structures, or would ...
user avatar
6 votes
0 answers
244 views

Are teaching-based tenure positions a unicorn in TCS?

I thought about asking this question over at academia.stackexchange, but reverted to posting here since is overly specific to TCS. I’m currently a fourth year PhD student in TCS in a top 4 school. So ...
user avatar
6 votes
0 answers
327 views

What is the current status of Acta Informatica?

Almost everybody knows the journal Acta Informatica. Some really important publications appeared there over the years. Upon looking on the website of the journal I noticed the following: Number of ...
user avatar
  • 780
6 votes
0 answers
430 views

What makes for a good paper abstract?

I am writing a paper for a TCS conference and wondering what the community's opinion is on how abstracts in TCS should be written, good practices, or rules of thumb. I thought that I had read enough ...
user avatar
  • 7,090
6 votes
0 answers
951 views

What should I do to switch from math department to cs to research tcs topics?

This can be a very weird question, but I haven't seen the same situation with mine in this forum, so I'd like to put this. Let me introudce my situation first. I'm now a math student of master ...
user avatar
  • 61
6 votes
0 answers
292 views

Formula in common: How to search for same/similar equations in other knowledge domains?

In a recent presentation by Sedgewick, he recounts in 1977 Flajolet noticed that they had a formula in common, both in different domains (see slide 4 in http://www.cs.princeton.edu/~rs/talks/AofA2AC....
user avatar
6 votes
0 answers
422 views

What is the origin and meaning of the phrase "Lambda the ultimate?"

I've been messing around with functional programming languages for a few years, and I keep encountering this phrase. I understand what lambda means, the idea of an anonymous function is both simple ...
user avatar
5 votes
0 answers
140 views

Program size versus program running time

Short "naive" question: Is it true that faster algorithms require longer programs ? Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) ...
user avatar
5 votes
0 answers
185 views

What research is being done in classical complexity theory?

As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
user avatar
  • 633
5 votes
0 answers
186 views

Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?

It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC. I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by ...
user avatar
  • 358
5 votes
0 answers
136 views

What is the significance of regarding the mutual exclusion problem as a problem of physics?

In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote Most computer scientists regard synchronization problems, such ...
user avatar
  • 2,319
5 votes
0 answers
237 views

Being a theoretician at a business university?

I'm currently on the job market and I've seen some open faculty positions in computer science at a business university (which is quite reputable among its kind). While the job opening doesn't ...
user avatar
5 votes
0 answers
121 views

conceptual tools for illustrating types of computation?

From time to time I come across concepts in programming that take a certain number of exposures to grasp. Things like: tail calls, futures, monads, coroutines, closures, call/cc. The common theme is ...
user avatar
  • 151
4 votes
0 answers
92 views

Simple randomized priority queue matching the Fibonacci heap time bounds?

Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.). Many classical worst-case ...
user avatar
4 votes
0 answers
169 views

The graph of problem reductions

A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
user avatar
4 votes
0 answers
112 views

Status of the Junta Problem (soft question)

Does the learning theory community in general believe that juntas can be learned in polynomial time? The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
user avatar
  • 187
4 votes
0 answers
102 views

Naming an algorithm after a copyrighted object

In machine learning, it is common to give algorithms quirky names. What happens if you think you've found a name that's actually quite fitting for an algorithm (catchy, descriptive, etc) -- but turns ...
user avatar
  • 10.1k
4 votes
0 answers
126 views

major applied focuses of different proof assistants

Currently, what are the major applied focuses (if any applications can be deserved such a distinction) of different proof assistants, such as the following? If there are significant differences ...
user avatar
4 votes
1 answer
158 views

Interesting programs on small machines

I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1 ...
user avatar
  • 41
3 votes
0 answers
115 views

Metrics for modelling convergence in the lambda-calculus

I wonder if there have been efforts to reconcile the measure approach to termination and Scott's domain theory or other topological models of computation. In other words, can we translate this measure ...
user avatar
3 votes
0 answers
191 views

Book recommendation treewidth

I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and ...
user avatar
3 votes
0 answers
184 views

How to write algorithms?

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
user avatar
3 votes
0 answers
664 views

Book Recommendations for a General Introduction to (Theoretical) Computer Science

After perusing the web and cstheory.stackexchange in particular, I've come across many different wonderful resources in Computer Science - from Sipser's "Introduction to the Theory of Computation" to ...
user avatar
3 votes
0 answers
104 views

Notion of "total work" of a problem?

I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction. I am curious if there is a theoretical notion of "...
user avatar
2 votes
0 answers
186 views

Quantum advantage beyond the black-box model

Question Aaronson wrote in his thesis that “essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic ...
user avatar
  • 395
2 votes
0 answers
396 views

Is Combinatory Logic (CL) still relevant for programming language theory?

I've been reading up on R. Smullyan's "To Mock a Mockingbird" and Hindley's "Lambda-Calculus and Combinators: An Introduction". I've even read Schonfinkel's 1924 paper introducing the idea of ...
user avatar
  • 5,165
2 votes
0 answers
56 views

None-monotone submodular function examples

What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?
user avatar
  • 239
2 votes
0 answers
247 views

Is putting articles on arXiv or alternatives, before peer review, generally acceptable?

How common is it to place articles on arXiv or similar sites before publishing in a peer-reviewed journal? I'm trying to get a feel for what my chances are, of publishing in a journal if I put an ...
user avatar
  • 2,080
1 vote
0 answers
55 views

Decision tree vs. pebble game lower bounds

This question concerns two types of lower bounds. In a pebbling lower bound, we are concerned with the complexity of constructing the output from the input. For example, if the only way we could ...
user avatar
  • 383
1 vote
0 answers
149 views

I think I may have discovered a new algorithm for a common problem. Now what?

I was trying to solve a common problem the other week and upon checking Stackoverflow there was a solution, but it just seemed like there should be a better way to do it. I thought about it for a ...
user avatar
1 vote
0 answers
26 views

Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
user avatar
  • 201
1 vote
0 answers
276 views

Automated theorem proving PhD

I'm looking for a university where I can do doctoral studies in automated theorem proving / computational algebra. Any ideas? Thank you!
user avatar
  • 119
1 vote
0 answers
82 views

"conservative approximate Set Cover"?

We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$). The task is to approximately cover $L$ with translated, rotated and flipped ...
user avatar
  • 131
1 vote
0 answers
1k views

How to find interesting algorithms to implement?

I am not a researcher in algorithms (I am a college freshman). I would like to implement an interesting recent algorithm from a data structure/algorithms paper. How can find a good algorithms paper ...
user avatar
0 votes
0 answers
319 views

What is the difference between a TCS PhD thesis and Computer Science experimental PhD thesis?

I'm doing my PhD in computer science, namely theoretical computer science and currently waiting for my VIVA. I think one of my examiner is an experimental person, how can I convince her that my work ...
user avatar
0 votes
0 answers
270 views

introduction to spectral geometry

In the paper Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps and spectral techniques for embedding and clustering." In NIPS, vol. 14, pp. 585-591. 2001 The ...
user avatar
0 votes
0 answers
396 views

Hardness of Happynet problem

I have been recently researching Happynet in terms of approximation and I have found out that there is a little interest in this topic. What's the reason for this? Are there any related problems, ...
user avatar