Guest post: TCS for All (previously TCS Women) Spotlight Workshop at STOC 2024/Theory Fest: Travel grants and call for speaker nominations.
Guest post by the organizers of TCS for All (previously TCS Women).
You are cordially invited to our TCS for All Spotlight Workshop! The workshop will be held on June 24, 2024, at 12:30 pm – 2 pm, and 4:15 pm – 5:45 pm in Vancouver, Canada as part of the 56th Symposium on Theory of Computing (STOC) and TheoryFest! The workshop is open to all.
More information about the workshop would be made available here: https://sigact.org/tcsforall/. In particular, we would like to highlight the TCS for All Travel Scholarships (deadline April 28th) and a call for nominations for Rising Stars talks at the workshop (deadline April 28th). More information on those are below.
Hope to see you in Vancouver!
TCS for All Travel Scholarship:
TCS for All Travel Scholarships are intended for researchers at the beginning of their career. This scholarship is being made available for minorities in TCS, and anyone who identifies as such is welcome to apply; this scholarship is open to both US and international students. Preference will be given to students at the beginning of their studies. If we have sufficient funding, we will give awards to more senior students and possibly even postdocs.
To apply, you will need to fill out the following form by April 28th, 2024 (11:59 pm PDT) in which you provide basic information about yourself, an estimate of your expenses, and a brief statement:
Apply for a travel grant here.
In addition, you will need to have your advisor (or department head or other faculty mentor if you do not yet have an advisor) send a letter of support to tcswomen@gmail.com by April 28th. Your advisor’s letter should also describe the availability of other travel funds. Note for advisors: Specifics about alternative funding are very helpful. Statements like “funding is tight” are not very helpful. This letter should be sent with the subject line “support letter for [your name]”. This is very important. Your application is not complete without this letter.
Late applications (after April 28th) will not be accepted. You will be notified about your status by May 5th, which is prior to the STOC early registration deadline and hotel cut-off deadline.
Notes: Receipts will be required for all travel awards, and reimbursements will be made after the conference. Food or visa expenses will not be reimbursed.
Nominations for Rising Star talks:
We invite nominations for speakers in our Rising Star talks at the TCS for All Spotlight Workshop at STOC 2024. To be eligible, your nominee has to be a senior PhD student with expected graduation no later than August 2024, or a postdoc in theoretical computer science (all topics represented at STOC are welcome), an underrepresented minority, and not a speaker at a previous TCS Women Spotlight Workshop. Preference will be given to speakers who are currently on the job market for postdoctoral/faculty positions, or who expect to be on the job market in Fall 2024.
You can make your nomination by filling this form by April 28th: https://forms.gle/WAZsXRm2wuxhdukK7
-approximate maximum flow problem in capacitated, undirected graphs with 
vertices and $m$ edges, achieving 
depth and 
work in the PRAM model. Although near-linear time sequential algorithms for this problem have been known for almost a decade, no parallel algorithms that simultaneously achieved polylogarithmic depth and near-linear work were known. At the heart of our result is a polylogarithmic depth, near-linear work recursive algorithm for computing congestion approximators. Our algorithm involves a recursive step to obtain a low-quality congestion approximator followed by a “boosting” step to improve its quality which prevents a multiplicative blow-up in error. Similar to Peng [SODA’16], our boosting step builds upon the hierarchical decomposition scheme of R\”acke, Shah, and T\”aubig [SODA’14]. A direct implementation of this approach, however, leads only to an algorithm with 
depth and 
work. To get around this, we introduce a new hierarchical decomposition scheme, in which we only need to solve maximum flows on subgraphs obtained by contracting vertices, as opposed to vertex-induced subgraphs used in R\”acke, Shah, and T\”aubig [SODA’14]. In particular, we are able to directly extract congestion approximators for the subgraphs from a congestion approximator for the entire graph, thereby avoiding additional recursion on those subgraphs. Along the way, we also develop a parallel flow-decomposition algorithm that is crucial to achieving polylogarithmic depth and may be of independent interest.
time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are 
[BLNPSSSW FOCS’20] and 
[AMV FOCS’20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS’01].
bound from over three decades ago [Gabow and Tarjan SICOMP’89].
which denotes the best volume-based lower bound on the covering radius 
of a convex body 
with respect to a lattice 
. Kannan and Lovász proved that 
and the Subspace Flatness Conjecture by Dadush (2012) claims a 
factor suffices, which would match the lower bound from the work of Kannan and Lovász.
. Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a 
-time randomized algorithm to solve integer programs in 
. Joint work with Thomas Rothvoss.
such that, for infinitely many values of 
outputs a canonical 
with high probability. More generally, we prove that for every dense property 
of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying 
TCS+ 