Integrated Calendar

What are the neural processes that lead to a decision to approach another individual in need and help them out of a tight spot? Multiple factors weigh in on this decision, including empathic arousal and social identity. The drive to act prosocially in response to others distress is evolutionarily rooted in mechanisms underlying parental behavior and group living. In humans, helping involves socio-emotional and cognitive components, and recruits brain regions involved in affective empathy arousal, executive function and motivation. This talk will present an overview of the rat Helping Behavior Test, which investigates the complex response leading to rescue of trapped conspecifics, and examine evidence to ask whether similar capacities are involved in rat helping. We’ll explore the idea that rat helping is motivated by empathy, what is the difference between social and prosocial reward, and whether helping is motivated by valuation of others’ outcomes. I will share what we’ve learned about the distinct neural network that is associated with empathy and prosocial behavior, and discuss findings of ingroup bias, adolescent helping, and interactions with rat immune function and wellbeing. We’ll ask what is the link between prosocial motivation and aggression, and what is the role of the social group in these behaviors.

In an influential paper, Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions (namely, distributions that can be sampled by a poly-size circuit). Trevisan and Vadhan showed that under a strong complexity theoretic hardness assumption, there are extractors for samplable distributions with large min-entropy of $k=(1-\gamma) \cdot n$, for some small constant $\gamma>0$. 

Recently, there has been significant progress in this area, and extractors for samplable distributions with much lower min-entropy were constructed.

In the talk, I will explain the motivation for extractors for samplable distributions, and the relation of this area to the well known area of worst-case to average-case hardness amplification. I will give a high level overview of the Trevisan-Vadhan construction, and will also explain some of the recent constructions.

This talk is based on several recent joint works with Marshall Ball, Justin Oh and Jad Silbak.

The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and $k$ designated terminals. The goal is to partition the vertices of the graph into~$k$ parts, each containing exactly one of the terminals, such that the sum of weights of the edges connecting vertices in different parts of the partition is minimized. The problem is APX-hard for $k\ge3$. The currently best-known approximation algorithm for the problem for arbitrary~$k$, obtained by Sharma and Vondr\'ak [STOC 2014] more than a decade ago, has an approximation ratio of 1.2965. We present an algorithm with an improved approximation ratio of 1.2787. Also, for small values of $k \ge 4$ we obtain the first improvements in 25 years over the currently best approximation ratios obtained by Karger, Klein, Stein, Thorup, and Young [STOC 1999]. (For $k=3$ an optimal approximation algorithm is known.)

Our main technical contributions are new insights on rounding the LP relaxation of C{\u{a}}linescu, Karloff, and Rabani [STOC 1998], whose integrality ratio matches Multiway Cut's approximability ratio, assuming the Unique Games Conjecture [Manokaran, Naor, Raghavendra, and Schwartz, STOC 2008]. First, we introduce a generalized form of a rounding scheme suggested by Kleinberg and Tardos [FOCS 1999] and use it to replace the Exponential Clocks rounding scheme used by Buchbinder, Naor, and Schwartz [STOC 2013] and by Sharma and Vondr\'ak. Second, while previous algorithms use a mixture of two, three, or four basic rounding schemes, each from a different family of rounding schemes, our algorithm uses a computationally-discovered mixture of hundreds of basic rounding schemes, each parametrized by a random variable with a distinct probability distribution, including in particular many different rounding schemes from the same family. We give a completely rigorous analysis of our improved algorithms using a combination of analytical techniques and interval arithmetic.

Joint work with Joshua Brakensiek, Neng Huang and Aaron Potechin.