text:
# 22.9: Balancing Redox Reactions- Oxidation Number Change Method

Sulfuric acid is produced in extremely large quantities in the United States (about 40 million tons/year). This material is manufactured by oxidizing sulfur to form sulfur trioxide. The $$\ce{SO_3}$$ is then dissolved in water to form the sulfuric acid. Most of the sulfuric acid produced is used in fertilizers. This acid is also found in lead-acid car batteries.

## Balancing Redox Reactions: Oxidation-Number-Change Method

One way to balance redox reactions is by keeping track electron transfer, by using the oxidation numbers of each of the atoms. For the oxidation-number-change method, start with the unbalanced skeleton equation. The example below is for the reaction of iron (II) oxide with carbon monoxide. This reaction is one that takes place in a blast furnace during the processing of iron ore into metallic iron:

$\ce{Fe_2O_3} \left( s \right) + \ce{CO} \left( g \right) \rightarrow \ce{Fe} \left( s \right) + \ce{CO_2} \left( g \right)\nonumber$

$\overset{+3}{\ce{Fe_2}} \overset{-2}{\ce{O_3}} \left( s \right) + \overset{+2}{\ce{C}} \overset{-2}{\ce{O}} \left( g \right) \rightarrow \overset{0}{\ce{Fe}} \left( s \right) + \overset{+4}{\ce{C}} \overset{-2}{\ce{O_2}} \left( g \right)\nonumber$

The carbon atom's oxidation number increases by 2, while the iron atom's oxidation number decreases by 3. As written, the number of electrons lost does not equal the number of electrons gained. In a balanced redox equation, these must be equal. So, the increase in oxidation number of one atom must be made equal to the decrease in oxidation number of the other.

Step 4: Use coefficients to make the total increase in oxidation number equal to the total decrease in oxidation number. In this case, the least common multiple of 2 and 3 is 6. So the oxidation-number increase should be multiplied by 3, while the oxidation-number decrease should be multiplied by 2. The coefficient is also applied to the formulas in the equation. So a 3 is placed in front of the $$\ce{CO}$$ and in front of the $$\ce{CO_2}$$. A 2 is placed in front of the $$\ce{Fe}$$ on the right side of the equation. The $$\ce{Fe_2O_3}$$ does not require a coefficient because the subscript of 2 after the $$\ce{Fe}$$ indicates that there are already two iron atoms.

Step 5: Check the balancing for both atoms and charge. Occasionally, a coefficient may need to be placed in front of a molecular formula that was not involved in the redox process. In the current example, the equation is now balanced.

$\ce{Fe_2O_3} \left( s \right) + 3 \ce{CO} \left( g \right) \rightarrow 2 \ce{Fe} \left( s \right) + 3 \ce{CO_2} \left( g \right)\nonumber$

## Summary

22.9: Balancing Redox Reactions- Oxidation Number Change Method is shared under a CK-12 license and was authored, remixed, and/or curated by CK-12 Foundation via source content that was edited to conform to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.


text:
Investing News

# Which Industries Have the Highest Inventory Turnover?

Inventory turnover measures the rate at which a company purchases and resells its products (or inventory) to its customers. Low inventory turnover can indicate bad management, poor purchasing practices or selling techniques, faulty decision-making, or the buildup of inferior or obsolete goods. As a result, investors usually don’t like to see a low inventory turnover ratio in a company; it can suggest the business is in, or headed for, trouble.

### Key Takeaways

• Inventory turnover is the speed with which a company purchases and resells its inventory.
• Slow inventory turnover could be a sign of poor management or inefficient purchasing practices.
• High volume, low margin industries—such as retailers—tend to have the highest inventory turnover.
• High inventory turnover can signal an industry as a whole is seeing strong sales or has efficient operations.

It is important to realize that low and high are only relative to the company’s particular sector or industry. No specific number exists to signify what constitutes a good or bad inventory turnover ratio across the board; desirable ratios vary from sector to sector (and even sub-sectors).

Investors should always compare a particular company’s inventory turnover to that of its sector, and even its sub-sector, before determining whether it’s low or high. For example, the industries that tend to have the most inventory turnover are those with high volume and low margins, such as retail, grocery, and clothing stores.

## Calculating Inventory Turnover

There are a couple of ways to calculate inventory turnover:

Inventory Turnover

=

Sales

Inventory

begin{aligned} &text{Inventory Turnover} = frac{ text{Sales} }{ text{Inventory} } \ end{aligned}

Inventory Turnover=InventorySales

Inventory Turnover

=

COGS

Average Value of Inventory

where:

COGS

=

Cost of goods sold

begin{aligned} &text{Inventory Turnover} = frac{ text{COGS} }{ text{Average Value of Inventory} } \ &textbf{where:} \ &text{COGS} = text{Cost of goods sold} \ end{aligned}

Inventory Turnover=Average Value of InventoryCOGSwhere:COGS=Cost of goods sold

Using the first method: If a company has an annual inventory amount of $100,000 worth of goods and yearly sales of$1 million, its annual inventory turnover is 10. This means that over the course of the year, the company effectively replenished its inventory 10 times. Most companies consider a turnover ratio between six and 12 to be desirable.

Using the second method: If a company has an annual average inventory value of $100,000 and the cost of goods sold by that company was$850,000, its annual inventory turnover is 8.5. Many analysts consider the costs of goods method to be more accurate because it reflects what items in inventory actually cost a company.

## Inventory Turnover Example

In sectors such as the grocery store industry, it is normal to have very high inventory turnover. According to CSIMarket, an independent financial research firm, the grocery store industry had an average inventory turnover of 17.11 (using the cost of goods method) for the first half of 2021, which means the average grocery store replenishes its entire inventory over 17 times per year.

This high inventory turnover is largely due to the fact that grocery stores need to offset lower per-unit profits with higher unit sales volume. These types of low-margin industries have proportionately higher sales than inventory costs for the year.

In addition to high volume/low margin industries needing a higher inventory turnover to remain cash-flow positive, a high inventory turnover can also signal an industry as a whole is enjoying strong sales or has very efficient operations. It is also a signal to investors that the sector is a less risky prospect since companies within it replenish cash quickly and don’t get stuck with goods that can become obsolete or outdated.

format: plain


text:
# DDA 2015 – Constraints on Titan’s rotation from Cassini mission radar data

This is one of a series of notes taken during the 2015 meeting of the AAS Division on Dynamical Astronomy, 3-7 May, at CalTech. An index to this series (all the papers presented at the meeting) is here.

Bruce Bills (JPL)

#### Abstract

We present results of a new analysis of the rotational kinematics of Titan, as constrained by Cassini radar data, extending over the entire currently available set of flyby encounters. Our analysis provides a good constraint on the current orientation of the spin pole, but does not have sufficient accuracy and duration to clearly see the expected spin pole precession. In contrast, we do clearly see temporal variations in the spin rate, which are driven by gravitational torques which attempt to keep the prime meridian oriented toward Saturn.

Titan is a synchronous rotator. At lowest order, that means that the rotational and orbital motions are synchronized. At the level of accuracy required to fit the Cassini radar data, we can see that synchronous rotation and uniform rotation are not quite the same thing. Our best fibng model has a fixed pole, and a rotation rate which varies with time, so as to keep Titan’s prime meridian oriented towards Saturn, as the orbit varies.

A gravitational torque on the tri-axial figure of Titan attempts to keep the axis of least inertia oriented toward Saturn. The main effect is to synchronize the orbit and rotation periods, as seen in inertial space. The response of the rotation angle, to periodic changes in orbital mean longitude, is modeled as a damped, forced harmonic oscillator. This acts as a low-pass filter. The rotation angle accurately tracks orbital variations at periods longer than the free libration period, but is unable to follow higher frequency variations.

The mean longitude of Titan’s orbit varies on a wide range of time scales. The largest variations are at Saturn’s orbital period (29.46 years), and are due to solar torques. There are also variations at periods of 640 and 5800 days, due to resonant interaction with Hyperion.

For a rigid body, with moments of inertia estimated from observed gravity, the free libration period for Titan would be 850 days. The best fit to the radar data is obtained with a libration period of 645 days, and a damping time of 1000 years.

The principal deviation of Titan’s rotation from uniform angular rate, as seen in the Cassini radar data, is a periodic signal resonantly forced by Hyperion.

#### Notes

• Titan:
• hard to see surface
• Cassini’s radar intended for mapping surface
• didn’t get much by way of repeat observations (“tie points”), which are needed to constrain rotation
• most data near poles — not terribly helpful
• Rotation model from tie-point observations
• Stiles et al. 2008: 50 tie points over 2.8 yr
• Now: 2602 tie points over 10 yr
• solve for 3 params (RA & DEC of spin pole, angular rate)
• $P = 15.94547727 \pm 6.03 \times 10^{-7}$ d
• spin pole precession
• gravity model: ~250 yr
• not clearly seen in data
• spin rate variations
• seen in data
• dynamical model
• assume Titan in synch. rotation
• gravity torque
• dissipation
• $\rightarrow$ libration period ~850 d
• Hyperion has nontrivial influence
• fit: libration period = 645.4 d, damping time = 430 yr, rotation period slightly changed


text:
# Why isn't this working? a simple inverse of a 2x2 matrix

1. Oct 3, 2005

### mr_coffee

Okay i have a simple problem, and its not working!
I have the following:
Find a 2x2 matrix
A =
-5 3
2 -9

A-1 =
-3/13 -1/13
2/39 -5/39

A*A-1 = I
1 0
0 1

but its saying the inverse i got is wrong! how is this?
det i got was 1/39

2. Oct 3, 2005

### amcavoy

Last edited: Oct 3, 2005
3. Oct 3, 2005

### mr_coffee

thanks for the responce!! But how did u get a det of -39? if a determinant is defined as
-5 3
2 -9

(-5)(-9) -(3)(2) = 45 - 6 = 39, and its under 1, so 1/39?
I also tried ur answer, when u say divide the adjoint matrix, do u mean divide the matrix after switching a and d, and negating b and c? I tried that and it was also wrong with ur det

4. Oct 3, 2005

### amcavoy

The determinant of a 2x2 matrix is ad-bc. I meant to say 39, not -39.

Last edited: Oct 3, 2005
5. Oct 3, 2005

No!


text:
{{ message }}

Instantly share code, notes, and snippets.

# Paul Rougieux paulrougieux

Created May 29, 2020
Git config
View .vimrc
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 """""""""""""""""""""""""" " Vundle package manager " """""""""""""""""""""""""" " Should be at the beginning set nocompatible " be iMproved, required filetype off " required " set the runtime path to include Vundle and initialize set rtp+=~/.vim/bundle/Vundle.vim call vundle#begin()
Last active Jan 24, 2020 — forked from fbiga/License.md
Load data from faostat bulk download into R data frames

MIT

Copyright 2020 Paul Rougieux, 2019 fbiga

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE 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 SOFTWARE

Created Nov 20, 2018
View spectrophotometer.txt
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 Group: Controls 1 Sample Wells Values MeanValue CV Od-bkgd-blank Anti-Hu Det A11 2.849 2.855 0.282 2.853 A23 2.860 Coat Control A12 0.161 0.160 0.530 0.159 A24 0.160 Diluent Standard 1 A9 0.114 0.113 1.379 0.104 A21 0.112 Diluent Standard 2 A8 0.012 0.013 2.817 0.012 A20 0.013
Created Jun 27, 2018
Variable do not persist in note book mode, but they persist when markdown is compiled
View pythonvariables.Rmd
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 --- title: "R Notebook" output: html_document: df_print: paged --- `{r setup, include=FALSE} knitr::opts_chunk\$set(echo = TRUE) library(reticulate)
Last active Jul 12, 2017 — forked from anonymous/warningerrorlog.R
Catch errors and warnings from log file
View warningerrorlog.R
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # Load the 2 functions below, # then test errors with: # downloadfile1(url="xxxx", destfile="/tmp/xxxx", logfile="~/rlog.txt") # ~/rlog.txt contains # Error in download.file(url = url, destfile = destfile, ...): cannot download all files # # then # # downloadfile2(url="xxxx", destfile="/tmp/xxxx", logfile="~/rlog.txt") # ~/rlog.txt contains the warning message
Last active Oct 3, 2021
Extract link texts and urls from a web page into an R data frame
Last active Jan 15, 2017
View testpagenumbers.lyx
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #LyX 2.1 created this file. For more info see http://www.lyx.org/ \lyxformat 474 \begin_document \begin_header \textclass scrbook \use_default_options true \begin_modules customHeadersFooters \end_modules \maintain_unincluded_children false
Last active Apr 15, 2016
dplyr::filter nse
View dplyrfilternse.R
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 library(dplyr) library(lazyeval) Species <- "virginica" # The Species variable is interpreted # in the context of the data frame iris %>% filter_(Species == Species) %>% nrow() # 150
Last active Feb 23, 2022
Use of the package threeparttable with Lyx
View threeparttable.lyx
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #LyX 2.1 created this file. For more info see http://www.lyx.org/ \lyxformat 474 \begin_document \begin_header \textclass article \begin_preamble \usepackage[flushleft]{threeparttable} \end_preamble \use_default_options true \begin_modules
Last active Nov 19, 2015
Add a footnote in a table generated by xtable inside a Lyx document (answer from http://stackoverflow.com/a/13676007/2641825)
View knitrchunk
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 <<1stgenerationxtunitroot, results='asis'>>= library(xtable) x <- matrix(rnorm(60), ncol = 10) x.big <- xtable(x,label='tabbig', caption='Example of longtable') names(x.big) <- LETTERS[1:10] names(x.big)[9] <- paste('I','footnote') # I put the tag on I letter print(x.big,tabular.environment='longtable',floating=FALSE, sanitize.text.function=function(str)gsub("footnote","\\footnote{my tricky footnote !!}",str,fixed=TRUE)) @


text:
# Complexity of sorting a 1-sorted array

A $k$-sorted array is one in which every element is at most distance $k$ from its position when the array is sorted. The complexity of sorting such array is $O(n\log k)$. But if $k=1$, then $\log k=0$ so what happens? What is the complexity of sorting an array where each element is at most one place away from its sorted position?

• If $k=1$ it means that either the minimum is the first element or the second one. Compare the two and eventually swap them. Now you have $n-1$ elements to sort and you can repeat the exact same reasoning. Thus in $n-1$ comparison you have sorted the array, so there's an $O(n)$ algorithm for that. – Bakuriu Mar 17 '16 at 19:22
• I will, since it seems to be clearer to everyone else. Why I did not is because in its non-edited version he did not answer what the actual complexity was and your answer helped me understand what I was missing (I was aware of disregarding low coefficients). Thank you. – blurry Mar 18 '16 at 15:33

When we say an algorithm runs in $O(\lg k)$ time, that is an asymptotic statement. It means that there exists a constant $c$ such that when $k$ is sufficiently large, the running time is $\le c \lg k$. It says nothing about what happens when $k$ is small.

In particular, if we say an algorithm runs in $O(\lg k)$ time, that doesn't necessarily mean that when $k=1$ the running time is 0.

The same kind of comment applies to your question as well. No, it doesn't mean that the running time to sort an array where each element is at most one place away from its sorted position is $O(0)$. Rather, the complexity of that task is $O(n)$.

There is hidden linear time to perform merge part of sorting algorithm.
Linear is less than loglinear, so it was not visible. $\log1=0$, but it means that you will not e.g. heapify, just merge in $O(n)$ (heap structure in case of 1-sorted array degrades to swapping consecutive elements to perform sort).

Inserting element to empty heap (which might be used in such sorting) costs $O(1)$, while putting element to min-heap containing $k$ elements is $O(\log k)$, which is in fact $O(\log k + c)$, so the first looks like it could be substituted with $k=1$ to have cost 0, but the second reveals constant factor in asymptotic notation.

• I find this answer very hard to understand. What do you mean by "reveal the hidden part and say it is $O(1)$"? The whole algorithm is $O(1)$? That can't be possible because the input could be arbitrarily long. – David Richerby Mar 17 '16 at 19:06
• The "heapify step" per one element is logk + c, but when k > 1 this is simply logk. When k = 1, we do not use heap so heapify step costs 0, but there is still assingment / read of variable which takes constant time. In notation O(k + 2) we write O(k), but when k = 0, we cannot say this costs nothing, because there are two operations, so I use O(1). – Evil Mar 17 '16 at 20:03
• I couldn't even understand this answer until I read D.W.'s. – stannius Mar 17 '16 at 21:32

There are some studies of tight bounds on sorting, such as Gagie and Nekrich, Tight bounds for online stable sorting , which looks at cost as a function of multiset entropy. These estimates include lower-order terms, so if you look at Table 1 you'll see that both upper bounds include an O(n) term in addition to Hn, so you can't just set H=0 and get zero cost. The O(n) is typically required to verify that all the elements are identical in the H=0 case (n-1 comparisons to be exact).

Unfortunately this makes sorting low-entropy sets disproportionately costly; for instance in radix sort when one radix is single-valued.

I think the entropy is also small for K-sorting; I don't know the exact expression offhand. If all the elements are already ordered that's similar to them being identical; n-1 comparisons are needed.


text:
# That elevator analogy

1. May 1, 2013

### Paintjunkie

So If I remember right. The explanation as to why people in orbit appear to be weightless is cause they are in free fall. and because they are in an innertail frame we see them as weightless.

this explanation bothers me some. cause I feel as though that innertail frame is still expieriencing gravity. if that inertial frame was no where near earth or any other large mass wouldnt we be able to tell the difference.

I guess I am thinking that since I am made of mass I have a gravitational pull. so if i let go of an apple it would orbit me, if i was no where near a larger body. but if I was on the space station and let go of an apple it would just fall with me. Am i thinking about this wrong?

2. May 1, 2013

### Travis_King

An apple wouldn't orbit you under any real, obtainable conditions.

3. May 1, 2013

### Staff: Mentor

You do indeed exert a gravitational force on objects near you like the apple. However, in these elevator/free-fall thought experiments we ignore your gravity, and instead assume that the only gravitational attraction that matters is that of the earth.

And as for why that's a valid assumption? Try calculating the gravitational force between you and a nearby apple using $F=\frac{Gm_{1}m_{2}}{r^2}$ where r is in meters, the two masses are kilograms, and G is about 6x10-11.... You're no more likely to notice it in outer space than you do here on earth.

4. May 1, 2013

### Paintjunkie

Ok, i get that the force between us would be almost nothing. but in a universe with only me and the apple wouldnt almost nothing, be alot? wouldnt the apple and I be attracted to each other over a really long time?

seems to me that in a free fall if the apple and myself were pulled into one another over a long time it would be purly coincidental.

I guess i am sort of changing my question by introducing long intervals of time...

5. May 1, 2013

### Staff: Mentor

In a universe with only you and the apple, the apple could perform a very slow orbit around you, indeed (something like 1 revolution per day). If it goes to fast, it will escape and you'll never see it again.

6. May 1, 2013

### Paintjunkie

situation 1) only me and apple - we orbit each other over time
situation 2) me apple and earth - me and apple orbit earth, but not each other

observed over time each situation will produce very different observations. so how is it that people can say free fall is like being weightless because of inertial frames or w/e.

7. May 1, 2013

### Travis_King

In orbit, we are not really that high up. We are still well within Earth's sphere of influence and, if I remember correctly, at the distance that the ISS orbits we are still experiencing something like 90% of the surface gravity. However, weight is a force (more specifically, a contact force). On Earth we feel heavy because the ground is exerting a force which is equal and opposite to the force exerted by Earth's gravitational acceleration (multiplied by our mass). When we are in orbit, however, we are in a free fall. There are forces acting on us (gravity), but that force goes into accelerating us (hence, the fall). There is nothing pushing against us, resisting the gravitational force, and therefore we are "weightless".

If you free fall in an elevator, you will feel weightless because the floor will be falling away from you at the same rate that you are being pushed into it. No force will be exerted on you by the elevator, and hence you will feel weightless. You still have mass. You are still accelerating at -9.81 m/s^2. But you have no weight because nothing is resisting your fall.

When you talk about actual circumstances (i.e. you and an apple in a space station) versus theoretical circumstances (i.e. you and an apple and that is it), you can get confused...

The force between the apple and you is extremely, extremely low, especially compared to the force between the apple and the Earth.

Edit: Also, you have the idea about "orbits" slightly wrong. Not everything will necessarily orbit. You need certain conditions of distance and speed in order to create a proper orbit. As mfb said, if the thing's got too much velocity, it will simply sail away into the abyss for eternity. If it's got too little velociy, it'll smack into you over time.

Last edited: May 1, 2013
8. May 1, 2013

### xAxis

Also, there is no difference between your two cases. If the apple orbits you in free space, it will orbit you even if you orbit a planet, given the same distance and relative speeds between you and an apple.

9. May 1, 2013

### Staff: Mentor

The apple will orbit you in both situations, it's really no different than the way the space station orbits the earth while the earth orbits the sun. However, the gravitational force between you and the apple is so weak and hence the orbital velocity of the apple around you is so small, that we don't really notice. Round numbers, if I haven't messed up doing the math in my head, an apple one meter from you will orbit you with a speed of a centimeter an hour or so, one orbit per month or thereabouts.

10. May 2, 2013

### Paintjunkie

thank you everyone. I will revise my thinking

11. May 2, 2013

### sophiecentaur

Actually, you could 'easily' arrange for a small ball bearing to close-orbit a steel* sphere of a metre radius and it would have a period of around 90minutes - same as a low Earth orbit.
I would love for someone to do that. Problem is that real spacecraft have a density as low as possible so the period of your apple would be months / years?. But satellites do actually interact and would mutually orbit if they were not kept on station - as do the bits of debris in Saturn's rings and the asteroid belt..

* or with a density equivalent to that of the Earth's average

12. May 2, 2013

### Staff: Mentor

A low earth orbit does not allow orbits of smaller objects around you. The problem is the inhomogeneous gravitational field of earth: it is not the same where you are and where the apple is. This effect is small within the scale of a human, but the mass of a human is small, too (here is the right place to insert jokes about mothers).
To get enough gravitational force to counter that, you would need a density of more than 100 times the density of lead. Alternatively, go into a higher orbit. It is no problem to orbit the moon, for example.
We even have this effect on larger scales: Moon is orbiting earth, while the system "earth+moon" orbits the sun.

13. May 3, 2013

### sophiecentaur

Interesting comment and it makes sense qualitatively. I assume the inhomogeneity you refer to due to ISL and not the mass distribution within the Earth? I can see that the variation of field due to ISL would depend upon the mini-orbit diameter and the diameter (and density) would give the highest possible mass of the satellite, which would give the local field due to the satellite. So are you implying that the satellite and its mini satellite would still be mutually attracted but that any orbit would not be stable?

The perturbation due to the earth would decrease as the gradient of its field ( an inverse cube law?) so, in a high orbit (GSO), the mini orbit would suffer less by a factor of at least three orders of magnitude (?) compared with LEO. By the time you get to the Moon, there is nearly a further three orders of magnitude reduction.

14. May 3, 2013

### Staff: Mentor

What is ISL?

The inhomogeneity is simply the radial field of earth - it gets weaker with increasing distance, and changes direction if you go in the horizontal direction.
It is not just stability, you do not get orbits at all - any system of masses would drift away as their orbits around earth are too different.
The Hill sphere gives a way to analyze this quantitatively. With conventional materials (density below 25g/cm^2), you have to go beyond the level of geostationary orbits to get orbits around your orbiting object.
Right.

15. May 4, 2013

### Popper

Let's consider two cases

Case #1 - You're in free-fall in a uniform gravitational field near an apple that is initially at rest relative to you.

Case #2 - You're in an inertial frame of reference which is far removed from any gravitational source (and thus in flat spacetime).

In case #1, and as measured in your free-fall frame, the apple will accelerate towards you at a finite (although small) rate of acceleration, call it a.

In case #1, and as measured in your inertial frame, the apple will accelerate towards you at a finite (although small) rate of acceleration, call it b.

Then if can be shown that a = b. Thus you cannot tell whether you're in free fall in a uniform gravitational field or in an inertial frame of reference in flat spacetime. The weak equivalence principle states that a uniform gravitational field is equivalent to a uniformly accelerating frame of reference. Of course this assumes that you're in a closed lab and not observing what is going on outside the lab and nothing can get inside the lab from the outside.

If the gravitational field is non-uniform, i.e. there are tidal gradients present in the field, then you'll be able to determine if you're in an inertial frame of reference in flat spacetime or in a non-uniform gravitational field so long as you either wait long enough to observe what's going on in the lab or if the lab is large enough so that you can oberver tidal accelerations of objects placed in your region of space. This is equivalent to saying that you're observing what's going on in a large enough region of spacetime. But if you have sensitive enough instruments you can always determine if you're in a non-uniform gravitational field.

Another phrasing of the equivalence principle states that a free-fall frame is locally equivalent to an inertial frame of reference.

The strong equivalence principle states that the laws of physics are the same in all coordinate systems/frames of reference. This requires that the laws of physics be stated in covariant form which means that they are expressed using tensors (and derivatives are covariant derivatives). There is a coordinte free way in which the laws of physics can be stated and that's using the geometric version of the law which uses tensors in their geometric form rather than their component form.

16. May 4, 2013

### sophiecentaur

ISL is Inverse Square Law. (I should have put it in full)
Thanks for that link to the Hill Sphere. That picture says it all and the graph for the planets is informative.
This puts me in mind of the threads I've read on the Horseshoe Orbit.


text:
# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
A new alternating minimization algorithm for total variation image reconstruction. (English) Zbl 1187.68665
Summary: We propose, analyze, and test an alternating minimization algorithm for recovering images from blurry and noisy observations with total variation (TV) regularization. This algorithm arises from a new half-quadratic model applicable to not only the anisotropic but also the isotropic forms of TV discretizations. The per-iteration computational complexity of the algorithm is three fast Fourier transforms. We establish strong convergence properties for the algorithm including finite convergence for some variables and relatively fast exponential (or $q$-linear in optimization terminology) convergence for the others. Furthermore, we propose a continuation scheme to accelerate the practical convergence of the algorithm. Extensive numerical results show that our algorithm performs favorably in comparison to several state-of-the-art algorithms. In particular, it runs orders of magnitude faster than the lagged diffusivity algorithm for TV-based deblurring. Some extensions of our algorithm are also discussed.

##### MSC:
 68U10 Image processing (computing aspects) 94A08 Image processing (compression, reconstruction, etc.) 65J22 Inverse problems (numerical methods in abstract spaces) 65K10 Optimization techniques (numerical methods) 65T50 Discrete and fast Fourier transforms (numerical methods) 90C25 Convex programming
##### Software:
RecPF; ForWaRD; FTVd
Full Text:


text:
Problem. Bugs happen. The common solution to this problem is to fix the bug and release a patch. Version 1.0 has bugs, version 1.0.1 fixes those bugs.

Inevitably at some point in time you will need to put together a list of all of the changes in a release. For me, this needs to go into a format we can post on our wiki. This process can be tedious if it is a manual process. There are a few approaches to handling this. You can go against the bug tracking repository and look for what bugs were fixed for this release. This will tell you everything that should have changed. I say ‘should have’ here because you cannot know for sure if the information is 100% accurate.

The other option is to go to the version control repository for information on what has change. This is the authoritative source of what has changed but often contains more information than what you would want in a change-log.

In my previous post on version control I mentioned that we have best practices around format for commit messages. All bugs start with the words “Bug <number:“. A change-log can be constructed from these entries in subversion. I wrote a simple groovy script that generates this change-log for me. It uses the subversion command line interface. The starting point is using the ‘svn log’ command. This command generates a change-log. Here are the options used to this command:

• The ‘–xml’ option is used to format the output as XML. This allows groovy to break it down easily.
• The ‘-g’ option is used which shows log messages from other revisions that were merged onto this branch. Let’s say you have 50 bugs that are merged onto the bug fix branch all at once. This would create a single revision on the branch. Using this option includes all 50 comments from their original commit on the trunk. This detail we want in the change-log. This gives nested entries though so the code has to handle that case.
• The ‘-r’ option is used to specify the revision range to use. In this case for a branch, we want from the previous release revision number to the current (or HEAD). For this example, let’s assume the 1.0 branch was at revision 1528.

The command to run then becomes:

svn log -r HEAD:1528 -g --xml

The next step that needs to be done is to take this XML and turn it into a change-log. I plan to use this as a comment into a wiki so I prefix the lines with ‘*’ so they will appear as a bulleted list in trac. It also puts the revision number at the end of the line in brackets. The output should look like this:

* Bug 123: Fixed some bug (1554)
* Bug 126: Some other issue (1588)
* Bug 322: Fixed the thing (1600)

To generate this changelog, I wrote a groovy script. It uses the svn command to generate the changelog and uses Groovy’s XML Parsing to break it up and format it. The path to the working directory and revision number would change from release to release but the rest of the code is reusable.

def handleEntry
handleEntry = {entry->
def message = entry.msg.text()
if (message.size() >= 3 && message[0..2].equalsIgnoreCase("bug")) {
println " * $message (${entry.@revision})"
}
entry.logentry.each(handleEntry)
}

def proc = "svn log -r HEAD:1528 -g --xml".execute(null, new File("/path/to/working/directory"))
new XmlParser().parseText(proc.text).logentry.each(handleEntry)


text:
Intel Research on Disclosure Gadgets at Indirect Branch Targets in the Linux* Kernel

Published: 11/03/2022

Last Updated: 11/10/2022

Blog by Scott Constable with contributions from the IPAS security team

About the author: Scott is a security researcher in Intel Labs. He received his PhD in computer science from Syracuse University in 2018. Scott’s current research covers instruction set architecture security and transient execution attack mitigation. He recently developed an optimized software mitigation technique for Load Value Injection (LVI); this approach has been adopted by LLVM/clang.

In March 2022, researchers at VU Amsterdam disclosed Branch History Injection (BHI) and Intra-Mode Branch Target Injection (IMBTI). Both are transient execution attacks that, as their names suggest, exploit the behavior of the hardware indirect branch predictor. The researchers demonstrated both attacks against a commodity Linux* kernel, though the attacks do require an adversary to be able to execute code locally on a victim machine. Intel has already provided guidance to mitigate BHI and IMBTI. One of our recommendations is to apply spot mitigations to any specific disclosure gadgets in privileged software (such as a kernel) that are found to be exploitable. We didn’t want to wait for someone else to trawl for exploitable gadgets, so we immediately set out to do our own analysis on the Linux kernel.

We did find some gadgets that initially looked promising—scroll down to see some examples. But we were not able to put together a working exploit with any of these gadgets. This is because BHI and IMBTI are complex attacks that require more than just a disclosure gadget, and in our experience it wasn’t feasible to combine all of the essential ingredients.

Intel defines a disclosure gadget as an instruction sequence that can execute transiently1 and both:

1. Access a victim’s secret
2. Transmit that secret over a covert channel

BHI and IMBTI can occur when an adversary is able to cause an indirect branch to predict to an indirect branch target that was previously reached within the same predictor mode. The branch target must contain a disclosure gadget that can execute before the processor detects the branch misprediction and squashes the pipeline2. The branch target may have been reached either architecturally or transiently.  However, this analysis assumes that the disclosure targets must be reached architecturally3.

Disclosure gadgets can be constructed using managed runtimes, including those that allow unprivileged users to generate and execute code in the kernel. This is precisely how the VU Amsterdam researchers demonstrated their BHI attack against the Linux kernel. Until recently, some Linux distributions would enable a feature called unprivileged eBPF by default, which allows unprivileged user programs to generate and execute code in a sandboxed environment within the Linux kernel. In their paper, the researchers describe how they were able to cause unprivileged eBPF’s just-in-time (JIT) compiler to generate disclosure gadgets that can be used to mount a BHI or IMBTI attack.

The VU Amsterdam researchers also conjectured that “potential disclosure gadgets” [1] (gadgets that are “not conclusively exploitable”) may also exist incidentally and unintentionally within the Linux kernel itself. They built a tool on the angr framework to find these potential disclosure gadgets and claimed to have identified 1,177 disclosure gadget candidates within the Linux kernel. At the time of this writing the list of candidates has not been published, and the researchers have not indicated that they have used any of the candidates to achieve a demonstrable exploit.

The analysis in this blog focuses on disclosure gadgets that use a cache covert channel to transmit data. In x86-64 assembly, such a disclosure gadget might look like this:

example_masked_disclosure_gadget:
shl   rax, 6                          # Shift by cache-line granularity
mov   ebx, WORD PTR [rax-0xdeadbeef]  # Transmit over covert cache channel

In this example, an adversary that controls the entire value in rdi can transiently load a byte, shift the byte by the CPU’s cache-line granularity ($$2^6=64$$ bytes), and then use the loaded byte as an index to access memory relative to an adversary-known location, such as -0xdeadbeef. This last operation, commonly referred to as a transmitter, encodes the loaded byte into the CPU’s caches by triggering a cache fill that can later be detected by a cache analysis technique such as Prime+Probe4. If the loaded byte is not zero/sign extended by movzx/movsx, or the upper bytes are not masked by other operations (such as a logical AND), then the address formed by the transmitter may be non-canonical and the transmitter will not transmit the loaded byte. When a disclosure gadget does mask the upper register bits, we refer to the gadget as masked; all other disclosure gadgets are unmasked.

example_unmasked_disclosure_gadget:
shl   rax, 6                          # Shift by cache-line granularity
mov   ebx, WORD PTR [rax-0xdeadbeef]  # Transmission only succeeds if

Linear Disclosure Gadgets: The Focus of This Analysis

When a masked gadget is not interposed by any conditional branch or procedure call, we refer to the disclosure gadget as linear. Of all the potential disclosure gadgets that may exist unintentionally within a given codebase, linear disclosure gadgets are the ones which are most like disclosure gadgets that could be intentionally constructed by an adversary.

Intel’s Analysis Approach

Concurrent with the VU Amsterdam research and prior to the March 2022 disclosure of BHI and IMBTI, we developed an LLVM-based5 static analysis tool that can scan indirect branch targets to identify potential disclosure gadgets that consist of an adversary-controlled load and a dependent cache covert channel transmitter with an adversary-controlled/knowable base address. Intel has open-sourced the analysis tool. Our objective was to investigate whether exploitable gadgets may exist in the Linux kernel, independent from code generated by unprivileged eBPF.

Our analysis tool uses LLVM’s Register Dataflow Framework to reconstruct a static single assignment form for each function that will be emitted into the final binary. At each indirect branch target, the tool identifies the set of live registers and then traverses the def-use chain beginning at each live register. The tool records dataflows consisting of:

<ipv4_conntrack_local>:
movzx  ecx,WORD PTR [rsi+0xb4]      # Load Secret
movzx  eax,WORD PTR [rcx+rax*1+0x6] # Transmit Secret

Analysis Results

We applied our analysis to the Linux kernel (v5.16, defconfig) built with link-time optimization (LTO) and LLVM’s default inlining threshold. We also analyzed several kernel modules. We scanned all indirect call targets, indirect jump targets, and return targets. The table below summarizes our results.

Table 1: Disclosure Gadget Candidate Analysis
Indirect Call 20,615 27,762 (9,334) 284 (145) 8 (8)
Indirect Jump 5,030 3,813 (1,767) 41 (134) 13 (13)
Return 262,401 63,888 (81,298) 928 (2,313) 55 (49)
Total 288,046 95,463 (92,399) 1,253 (2,592) 76 (70)

First, let’s discuss the indirect call and jump targets. In total, the scanning tool identified 25,645 indirect call/jump targets within the Linux kernel and its modules. Not all targets are reachable via system calls or other user-facing utilities. Of these 25,645 targets, 11,101 have at least one potential disclosure gadget, and there are a total of 31,575 potential disclosure gadgets. Among these, the tool found 325 potential masked disclosure gadgets reachable from 179 indirect jump/call targets. Many of the masked gadgets pass through one or more conditional branches, and/or pass across one or more procedure calls. Either of these conditions implies that the gadget is non-linear. There are 21 potential linear gadgets at 21 indirect call/jump targets. Remember, the linear gadgets do not pass through any conditional branches or across any procedure calls. The 13 linear gadgets at indirect jump targets are all reachable from a single jump table within the ___bpf_prog_run() eBPF function. Since unprivileged eBPF is disabled by default in the Linux kernel, as long as unprivileged eBPF remains disabled, it seems unlikely that malicious user-mode software could steer the Linux kernel to reach these targets.

Now, let's consider the return targets, which in some situations can also be relevant for these styles of attacks. Predictions for RET instructions are typically made using the return stack buffer (RSB). However, when the RSB underflows, some processors may use the indirect branch predictor to predict the return target, as described in Retpoline: A Branch Target Injection Mitigation. If that prediction is incorrect, then the correct return target may be “remembered” by the indirect branch predictor and could later be used to predict the target of another indirect branch. Our tool found a total of 95,463 potential disclosure gadgets at 92,399 return targets. Among these gadgets, 55 are linear. At the time of this writing, it isn’t clear that any of these return target gadgets could be exploited in a BHI or IMBTI attack. Whereas indirect call/jump targets enter the indirect branch predictor when an indirect call/jump to the target is executed, return targets only enter the indirect branch predictor when the RSB underflows. Hence, in addition to identifying a suitable disclosure gadget at a return target, the adversary must also be able to steer the kernel to that return target in a call stack deep enough to underflow the RSB.

What follows next is a deep dive into some of the potential gadgets that our tool found. We describe all 8 of the linear gadgets that we found at indirect call targets. For brevity, we describe 1 of the 55 linear gadgets that we found at return sites. For the reasons discussed above, we don’t think that any of the indirect jump target linear gadgets are exploitable, so we don’t describe those here.

It’s worth noting first that none of the indirect call targets with a linear gadget are reachable for a malicious user-mode adversary with a default Linux kernel configuration. We haven’t applied a similar analysis to the potential gadgets at return targets, though it’s worth re-emphasizing that they must also be reached in a deep call stack.

And as a note for readers who aren’t as familiar with assembly code, we have written all of the code snippets using Intel assembly syntax, where the destination operand precedes the source operand. For example, mov rax, rbx means “move from rbx to rax.”

Suppose that the adversary controls the value in rdi at the indirect branch that mispredicts to hctx_type_show. Then the adversary can load a word at a chosen memory address and transmit bits 3:15 of the word over a cache covert channel with a fixed base address at -0x7dbd7bb0:

<hctx_type_show>:
movzx  eax, WORD PTR [rdi+0xfc]           # Load Secret
mov    rdx, QWORD PTR [rax*8-0x7dbd7bb0]  # Transmit Secret

The corresponding source code is shown below, where the shape of the disclosure gadget is visually apparent. The operation hctx_types[hctx->type] loads the unsigned 16-bit word hctx->type from memory, and then uses this value to index into the pointer array hctx_types:

static const char *const hctx_types[] = {
[HCTX_TYPE_DEFAULT]	= "default",
[HCTX_TYPE_POLL]	= "poll",
};

static int hctx_type_show(void *data, struct seq_file *m)
{
struct blk_mq_hw_ctx *hctx = data;

BUILD_BUG_ON(ARRAY_SIZE(hctx_types) != HCTX_MAX_TYPES);
seq_printf(m, "%s\n", hctx_types[hctx->type]);
return 0;
}

This function is part of Linux’s debugfs. A user typically requires root/sudo privilege to invoke hctx_type_show. We confirmed that this function can be reached as a root/sudo user by invoking the following command:

\$ cat /sys/kernel/debug/block/sda/hctx0/type

Assume that the adversary controls the value in rdx at the indirect branch site. Then this linear gadget can potentially transmit 3 bits out of each adversary-chosen byte. However, two of these bits are transmitted at sub-cache-line granularity, and therefore cannot be inferred by an adversary with a cache analysis technique such as Prime+Probe5 . Another issue with this gadget is that it can only be reached when Linux’s mq-deadline I/O scheduler is enabled.

<dd_merged_requests>:
push   r15
push   r14
push   r12
push   rbx
mov    rbx, rdx
mov    r14, rdi
mov    rax, QWORD PTR [rdi+0x8]
mov    r15, QWORD PTR [rax+0x8]
movzx  eax, WORD PTR [rdx+0x7e]        # Load Secret
shr    rax, 0xb                        # Loses bits 0:10 of Secret
and    eax, 0x1c                       # Loses bits 11:12 of Secret
mov    eax, DWORD PTR [rax-0x7dc20e50] # Transmit bits 13:14,
# but within a cache line;
# bit 15 determines whether the
# cache line at -0x7dc20e00 or
# at -0x7dc20e40 is accessed

Assume that the adversary controls the value in rdi at the indirect branch site and the kernel memory to which rdi points. Specifically, [rdi-0x70] should contain a pointer P to adversary-controlled kernel memory, wherein [P+0x20] contains another pointer Q to 26 bytes below the adversary-chosen secret, and [P+0x1c]=0 and [P] contains the base address for the transmitter. Hence, the adversary can load a chosen word and transmit bits 6:15 of the word over a cache covert channel relative to an adversary-chosen base address.

This gadget can only be reached if the e1000 driver is in use (that is, when the machine is using an e1000 device).

<e1000_clean>:
push   rbp
mov    rbp, rsp
push   r15
push   r14
push   r13
push   r12
rbx
and    rsp, 0xfffffffffffffff0
sub    rsp, 0x100
mov    rax, QWORD PTR gs:0x28
mov    QWORD PTR [rsp+0xf0], rax
mov    DWORD PTR [rsp+0x4c], 0x0
mov    r13, QWORD PTR [rdi-0x70]      # Load P into r13
mov    r12, QWORD PTR [rdi+0x1c8]
mov    eax, DWORD PTR [r13+0x1c]      # Load 0 into eax
mov    rcx, QWORD PTR [r13+0x20]      # Load Q into rcx
lea    rdx, [rax+rax*4]               # rdx=0
movzx  edx, WORD PTR [rcx+rdx*8+0x1a] # Load Secret into edx
mov    rbx, rdx                       # Copy Secret into rbx
shl    rbx, 0x4                       # Shift Secret by 4 bits
lea    r8, [rcx+rbx*1]
xor    r14d, r14d
test   BYTE PTR [rcx+rbx*1+0xc], 0x1  # Transmit Secret

In this linear gadget, the base address and secret are loaded from two distinct adversary-controlled registers that alias to the same memory address. Therefore, the adversary may not be able to control the transmitter. And, similar to the prior gadget, this gadget can only be reached if the e1000e driver is in use.

This gadget can be reached when the e1000e driver is loaded and being used to drive newer “packet-split”-enabled e1000e devices.

<e1000_clean_rx_irq_ps>:
push   rbp
push   r15
push   r14
push   r13
push   r12
push   rbx
sub    rsp, 0x70
mov    rbp, rdi                 # rbp and rdi point to the same address
mov    rax, QWORD PTR [rdi]
mov    QWORD PTR [rsp+0x10], rax
movzx  r13d, WORD PTR [rbp+0x22]      # Load Secret
mov    rcx, r13
shl    rcx, 0x5
mov    ebx, DWORD PTR [rdi+rcx*1+0x8] # Transmitter is neither
# knowable

Assume that the adversary controls the value in rdi at the indirect branch site. The adversary must be able to form an address that will serve as both the address from which to load the secret, and as the base address for the transmitter. This gadget is that it can only be reached when Linux’s kyber I/O scheduler is enabled.

<kyber_bio_merge>:
push   rbp
push   r15
push   r14
push   r12
push   rbx
mov    r14, rsi
mov    eax, DWORD PTR gs:[rip+0x7eb7b15e]        # 15560 <cpu_number>
mov    eax, eax
mov    rcx, QWORD PTR [rax*8-0x7db05830] # Adversary must be able to
# deduce rcx
add    rcx, QWORD PTR [rdi+0x38]  # rcx will become the base address
# and the address of the secret,
# so the Adversary should choose
# X=[rdi+0x38] such that the desired
# address is equal to X plus the
# previous value of rcx
mov    eax, DWORD PTR [rsi+0x10]
xor    esi, esi
test   al, al
sete   sil
test   eax, 0x1000000
mov    edi, 0x2
cmove  rdi, rsi
mov    r15d, edx
mov    rbp, QWORD PTR [rcx+rdi*8+0x50] # Load (&Secret – 0xfc)
mov    rdx, QWORD PTR [rbp+0xb0]
mov    rbx, QWORD PTR [rdx+0x50]
movzx  edx, WORD PTR [rbp+0xfc]        # Load Secret
movzx  ecx, WORD PTR [rcx+rdx*2+0x44]  # Transmit Secret

Assume that the adversary controls the value in rdi at the indirect branch site. Then the adversary can load a word at a chosen memory address and transmit a value (using rdi as a base address) computed using the loaded word. This gadget is in the 802.11 stack and may be reachable through I/O or interrupts if the system has a corresponding 802.11 device.

The value transmitted is: (Secret >> 4) * 0xfc + (Secret & 0xf) * 0x18.

<minstrel_ht_get_expected_throughput.llvm.4422275375963575374>:
movzx  ecx, WORD PTR [rdi+0x14]        # Load Secret
mov    rsi, rcx
shr    rsi, 0x4
mov    r9d, ecx
and    r9d, 0xf
imul   rax, rsi, 0xfc
lea    rdx, [r9+r9*2]
movzx  r8d, WORD PTR [rax+rdx*8+0x104] # Transmit a value computed
# using Secret

Assume that the adversary controls the value in rdi at the indirect branch site, and rdi points to adversary-controlled memory. Then the adversary can load a word at a chosen memory address and transmit bits 1:15 of the word over a cache covert channel with a fixed base address. However, this function is only executed a single time at either boot or on PCI hot-plug events. That limits how often this gadget can be used; to how often PCIe hotplug operations are performed.

<tg3_start_xmit>:
push   rbp
push   r15
push   r14
push   r13
push   r12
push   rbx
sub    rsp, 0xc0
mov    r14, rsi
mov    rax, QWORD PTR gs:0x28
mov    QWORD PTR [rsp+0xb8], rax
movzx  eax, WORD PTR [rdi+0x7c]         # Load Secret
mov    r9, QWORD PTR [rsi+0x380]
lea    r10, [rax+rax*4]
shl    r10, 0x6
imul   r13, rax, 0x2c0                  # Multiply Secret by 704
lea    rbp, [rsi+r13*1]                 # rbp <- rsi + (Secret * 704)
mov    rax, QWORD PTR [rsi+0x1b10]
shr    rax, 0x3d
and    eax, 0x1
imul   r12, rax, 0x2c0
mov    ebx, DWORD PTR [r12+rbp*1+0xc40] # Transmit (Secret * 704)

Assume that the adversary controls the value in rdi at the indirect branch site, and the adversary either controls or has a way to know the value of rsi and the value of the memory to which rsi points. Then the adversary can load a word at a chosen memory address and transmit the word over a cache covert channel with an adversary controlled/knowable base address.

This gadget can only be reached if the system has a Tigon3 network interface controller (NIC).

<tg3_start_xmit>:
push   rbp
push   r15
push   r14
push   r13
push   r12
push   rbx
sub    rsp, 0xc0
mov    r14, rsi
mov    rax, QWORD PTR gs:0x28
mov    QWORD PTR [rsp+0xb8], rax
movzx  eax, WORD PTR [rdi+0x7c]         # Load Secret
mov    r9, QWORD PTR [rsi+0x380]
lea    r10, [rax+rax*4]
shl    r10, 0x6
imul   r13, rax, 0x2c0                  # Multiply Secret by 704
lea    rbp, [rsi+r13*1]                 # rbp <- rsi + (Secret * 704)
mov    rax, QWORD PTR [rsi+0x1b10]
shr    rax, 0x3d
and    eax, 0x1
imul   r12, rax, 0x2c0
mov    ebx, DWORD PTR [r12+rbp*1+0xc40] # Transmit (Secret * 704)

If the user-mode adversary can steer the kernel to return from __memcpy() to the highlighted code while causing the RSB to underflow, then the address of the movzx instruction may be “remembered” by the indirect branch predictor and could be used to predict the target of a later indirect branch. If the adversary can find another indirect branch within the kernel that satisfies the remaining requirements for BHI or IMBTI (see Closing Thoughts below), and the adversary controls both the register contents of rbx and the contents of the kernel stack pointed to by rsp, then the adversary can potentially use this gadget to load and transmit bits 6:15 of the word stored at rbx+0x1d2.

<nfs4_submount>:
call   ffffffff81d4b9b0 <__memcpy>
movzx  eax,WORD PTR [rbx+0x1d2]
mov    rcx,QWORD PTR [rsp]
mov    BYTE PTR [rax+rcx*1+0x1],0x0

Closing Thoughts

We began with no notion of what we might find. Would there be thousands of disclosure gadgets? None? A handful? And are they exploitable? Even with all of the analysis above, the answer is complicated because the disclosure gadget is only one of several components required to launch a successful BHI or IMBTI attack. At a minimum, to execute a BHI or IMBTI attack the adversary must be able to satisfy all of the following conditions:

• Execute code locally on the victim machine.
• Find a suitable disclosure gadget that is reachable within the current running kernel and given the privileges delegated to the adversary’s process (for example, utilities like seccomp can restrict which system calls can be invoked by a process).
• The disclosure gadget must be in code configured to be a part of the kernel. This results in code that is either built into the kernel image or present in a loadable module. In general, loadable modules are not loaded for hardware which is not present in the system. Most of the discussed disclosure gadgets are in code which is typically built as a loadable module. For example, a system not using NFS4 would be unlikely to even have the nfs4_submount gadget in memory.
• Find the location within the kernel where a secret is located. This may require the adversary to first break kernel address space layout randomization (KASLR) and/or perform other surveillance on the victim platform.
• Invoke a system call, trigger an interrupt or exception, etc. to steer the kernel to reach the disclosure gadget.
• Invoke another system call to trigger an indirect branch misprediction to the disclosure gadget with adversary-controlled register contents (or other processor context) that align with the disclosure gadget’s inputs. Steering the misprediction to the desired disclosure gadget may require the adversary to create aliasing in either the branch history buffer (for a BHI attack) or the branch target arrays (for an IMBTI attack). More details can be found in Intel’s BHI and IMBTI security guidance.
• Slow or stall the CPU pipeline at the right time to create a speculation window large enough for the entire disclosure gadget to execute transiently.
• Use a side-channel analysis technique such as Prime+Probe to recover the data transmitted by the disclosure gadget, while accounting for factors such as noise created by other workloads running on the system.

This is a lot to put together. We tried to build a PoC to exploit some of the reachable gadgets that we found, but we were unsuccessful. This doesn’t mean that BHI/IMBTI using a disclosure gadget in the Linux kernel is impossible—we can’t prove a negative. But it certainly is not trivial to execute.

A Note on How We Count Gadgets

We characterize a gadget by its access operation. For example:

• If an access propagates to two transmitters, it is counted as a single gadget.
• If an access is reachable from two different indirect jump targets, it is counted as a single gadget.

A branch target is counted if any gadget is reachable from that branch target. For example, suppose a function has a single gadget that is reachable from two different indirect jump targets. Then our tool would report for that function that two indirect jump targets have at least one reachable gadget.

References

1. E. Barberis, P. Frigo, M. Muench, H. Bos and C. Giuffrida, "Branch History Injection: On the Effectiveness of Hardware Mitigations Against Cross-Privilege Spectre-v2 Attacks," in USENIX Security 22, Boston, MA, 2022.
2. J. Wikner and K. Razavi, "RETBLEED: Arbitrary Speculative Code Execution with Return Instructions," in 31st USENIX Security Symposium (USENIX Security 22), Boston, MA, 2022.
3. A. Moghimi, J. Wichelmann, T. Eisenbarth and B. Sunar, "MemJam: A False Dependency Attack Against Constant-Time Crypto Implementations," International Journal of Parallel Programming, vol. 47, no. 4, pp. 538-570, 2019.
4. O. Kirzner and A. Morrison, "An Analysis of Speculative Type Confusion Vulnerabilities in the Wild," in 30th USENIX Security Symposium (USENIX Security 21), 2021.

Footnotes

1.  Instructions execute transiently when they execute but do not commit to architectural processor state. These transient instructions can sometimes affect microarchitectural processor state in a manner that can later be observed through timing analysis techniques such as Prime+Probe.
2. There are other variants of Branch Target Injection (BTI) that share this requirement: that the adversary must be able to find a disclosure gadget at a reachable indirect branch target within the kernel. One such example is Retbleed [2].
3.  Intel’s guidance on BHI and IMBTI states that predictor entries created in the same predictor mode “may contain targets corresponding to the targets of indirect near jump, indirect near call and/or near return instructions, even if these branches were only transiently executed” [emphasis added]. For example, suppose that debugfs is not mounted, and therefore the kernel would not be expected to call Linear Gadget #1: hctx_type_show. If a malicious user-mode adversary can cause an indirect branch in the kernel to speculatively execute hctx_type_show (for example, by using speculative type confusion [4]), then the adversary may be able to use BHI or IMBTI to subsequently cause a different indirect branch in the kernel to use this predictor entry to speculatively execute hctx_type_show. This might be useful if the adversary does not control the contents of rdi at the former indirect branch, but does control the contents at the latter indirect branch. To simplify our analysis, we focused on indirect branch targets that are architecturally reachable. Whenever we say that a gadget “can be reached” or “is reachable,” we mean that the target is architecturally reachable.
4. There are also sub-cache-line-granularity side channels, such as Memjam [3].
5. Most commodity Linux kernels are built with gcc. Since our analysis uses an LLVM-based compiler pass, the results we obtained may not be representative of a Linux kernel built using gcc.

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.


text:
# Expected value based on periodical interval measurements

Suppose you want to measure a process that goes on/off every 100ms +- rand 3000ms. Your tools can do probes ones in >=1500ms. How to get expected values of:

• how long the process is off
• how often the process goes off
• Well, suppose I can run simulations and gathering some data. Could it help me with? – trupanka Jun 18 at 21:33


text:
# What is $\ \overline{\bigcup_{p≥ 1}\ \{A\in M_n(\mathbb C), \ A^p = I_n\}} \$?

Let $\Gamma_p = \{A\in M_n(\mathbb C), A^p = I_n\}$ and let $\Gamma = \bigcup_{p≥ 1}\ \Gamma_p$.

What is the closure of $\Gamma$ ? (This is from an oral exam).

Let $B \in M_n(\mathbb C)$ such that there exists a sequence $(A_k)_k$ of elements of $\Gamma$ such that $A_k \to B$.

$\chi_{A_k} \to_{k\to\infty} \chi_B$ ($\chi$ is the characteristic polynomial). We will prove that each eigenvalue $\lambda$ of $B$ satisfies $|\lambda | =1$. Writing $\chi_{A_k} = \prod_{1 ≤ i ≤ n}(X-a_{i,k})$, with $|a_{i,k}|=1$ for all $i$ and $k$ ;

all $(a_{i,k})_k, 1≤i≤n,$ are bounded so we can apply Bolzano-Weierstrass theorem in $\mathbb C^n$ to prove there exists $\phi$ an extraction such that $a_{i, \phi(k)} \to_{k\to\infty} l_i$ for all $i$, $1≤i≤n$.

$\chi_{A_{\phi(k)}} \to_{k \to \infty} P$ and the roots of $P$ are the limits $l_i$ of $a_{i, \phi(k)}$, hence $|l_i|=1$ for all $i$. Otherwise $\chi_{A_{\phi(k)}} \to \chi_B$, hence $\chi_B = P$.

Reciprocally, suppose $B$ is such that for all eigenvalue $\lambda,$ $|\lambda| =1$.

$B = P^{-1}TP$ with $T$ being upper triangular. For every diagonal coefficient $t_i$ of $T$, $t_i$ is one of the eigenvalue of $B$, hence $|t_i|=1$.

For all $t_i$, we consider a sequence of roots of $1$ $(a_{i,k})_k$ such that $a_{i,k} \to_{k\to\infty} t_i$ and we choose these sequences such that for all $k$ and for all $(i,j), \ 1 ≤ i < j≤ n$, $a_{i,k} \neq a_{j,k}$ (using the density of the roots of $1$ in the unit circle).

Let $A_k$ be the upper triangular matrix with diagonal coefficient $i$ equal to $a_{i,k}$ for $1 ≤ i ≤ n$ and the other coefficients equal to the ones of $T$.

We will prove that for all $k$, there exists $p_k ≥ 1$ such that $A_k^{p_k} = I_n$ :

For all $i$ there exists $p_{i,k}$ such that $a_{i,k}^{p_{i,k}} = 1$.

Let $p_k$ be a common multiple of the $p_{i,k}, 1 ≤ i ≤ n$.

$\chi_{A_k} = \prod_{1 ≤ i ≤ n}(X-a_{i,k})$ vanishes $A_k$ and the $a_{i,k}, \ 1 ≤ i ≤ n$ are distinct, hence $X^{p_k} - 1$ vanishes $A_k$ i.e. $A_k^{p_k} = I_n$.

Finally, $(P^{-1}A_kP)_k$ is a sequence of $\Gamma$ (because $(P^{-1}A_kP)^{p_k} = I_n$) that converges towards $B$ since $A_k \to T$.

Is that correct?

• Your argument seems correct to me, for what that's worth. – Omnomnomnom May 17 '18 at 13:04
• Does the bar over $\Gamma$ refer to the complex conjugate? – Doubt May 17 '18 at 15:02
• @Doubt: It is the closure in topology. – user371663 May 17 '18 at 15:05


text:
# syntax question

## Recommended Posts

some odd syntax ive seen but not sure what it does. 1) int foo() = 0; 2) int foo( int a=5 ){ //stuff } 3) class foo { int a; foo a=5:(){ //stuff } // not sure if i even typed this one right... }

##### Share on other sites
1. That's a declaration of a "pure virtual function".
2. That's a declaration of a function with a "default argument".
3. That looks kind of like a (mistyped) example of an "initializer list".

Look up each of those in your C++ book.

##### Share on other sites
the second one you listed (as Sneftel pointed out) is a default argument. anway, basically it gives you an option on weather or not to send that argument, and if you dont, it will be assigned to the default. example:

void Test(int x = 0){   cout << x << endl;}

usage:
Test(5); //prints out 5Test(); //prints out 0Test(40); // prints out 40

##### Share on other sites
1. Forces a virtual function to be derived to be used. Ie. you can't call it in a base class. The function must be declared virtual or it won't compile:

class CBase {
public:
CBase() {
};

virtual void Function() = 0; //Can't call it from a CBase variable
};

class CDeriv {
public:
CDeriv() {
};
void Function() {
cout << "Stuff\n";
}
};

2. That sets a default value
3. You typed it wrong. Anyway, it sets the value of the variable.

class foo {
int a;
foo():a = 5 {
};
};

##### Share on other sites
I see... Thank you very much for all your replies.

I was looking at the Enginuity articles here on GameDev
and these kept popping up in his code, and i wasn't sure what
they did, but now i understand.
Thanks.

##### Share on other sites
Quote:
 Original post by MetaCipher3. You typed it wrong. Anyway, it sets the value of the variable.class foo { int a; foo():a = 5 { };};

You did too.

"foo() : a(5) {};"

The whitespace doesn't matter of course, but you don't use assignment statements in the initializer list - instead it uses that constructor-call-like syntax.

##### Share on other sites
Quote:
Original post by Zahlman
Quote:
 Original post by MetaCipher3. You typed it wrong. Anyway, it sets the value of the variable.class foo { int a; foo():a = 5 { };};

You did too.

"foo() : a(5) {};"

The whitespace doesn't matter of course, but you don't use assignment statements in the initializer list - instead it uses that constructor-call-like syntax.

Whoops, you are right. I was in a rush when I replied to this. You use paranthesis to assign values in the construct not an equal sign. (Like Zahlman has it)

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
627701
• Total Posts
2978709

• 21
• 14
• 12
• 10
• 12


text:
# PROVO-O in QUDT

Date: Thu, 1 Nov 2012 00:14:43 -0700

The NASA QUDT (Quantities, Units, Dimensions and data Types) Ontologies have been using PROVO-O.  This thread serves as a record of issues that may arise in our use of PROV-O.

An example of the use of prov:wasInfluencedBy is shown in the definition for unit:Abfarad below. QUDT also uses prov:wasDerivedFrom to trace how SI units developed from m.k.s. and c.g.s systems of units. The documentation of QUDT uses LaTeX encodings, as shown in the qudt:description statement below with the $bracketed expressions. unit:Abfarad a qudt:CapacitanceUnit , qudt:CGS-Unit ; rdfs:isDefinedBy <http://qudt.org/vocab/unit/cgs> ; rdfs:label "Abfarad"^^xsd:string ; qudt:abbreviation "abF"^^xsd:string ; qudt:code "0015"^^xsd:string ; qudt:conversionMultiplier 1.0E9 ; qudt:conversionOffset "0.0"^^xsd:double ; qudt:description "An abfarad is an obsolete electromagnetic (CGS) unit of capacitance equal to$10^{9}$farads (1,000,000,000 F or 1 GF). The absolute farad of the e.m.u. system, for a steady current identically$\frac{abC}{abV}$, and identically reciprocal abdaraf.$1 abF = 1 GF\$."^^xsd:string ;
qudt:designator "U-150-0015"^^xsd:string ;
qudt:isUnitOfSystem qudt:SOU_CGS-EMU ;
qudt:quantityKind quantity:Capacitance ;
qudt:symbol "abF"^^xsd:string ;
prov:wasInfluencedBy
<http://www.oxfordreference.com/view/10.1093/acref/9780198605225.001.0001/acref-9780198605225-e-13> .

We are currently in the process of producing the NASA QUDT Handbook. An update of the 1.2 to the QUDT website will happen before the end of the year. The current site http://qudt.org points to the published version 1.1, whose catalog is at http://www.linkedmodel.org/catalog/qudt/1.1/index.html.

Regards,
Ralph Hodgson, @ralphtq

Mobile Phone: +1 781-789-1664


text:
## CryptoDB

### Paper: Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift

Authors: Ann Hibner Koblitz Neal Koblitz Alfred Menezes URL: http://eprint.iacr.org/2008/390 Search ePrint Search Google Over a period of sixteen years elliptic curve cryptography went from being an approach that many people mistrusted or misunderstood to being a public key technology that enjoys almost unquestioned acceptance. We describe the sometimes surprising twists and turns in this paradigm shift, and compare this story with the commonly accepted Ideal Model of how research and development function in cryptography. We also discuss to what extent the ideas in the literature on "social construction of technology" can contribute to a better understanding of this history.
##### BibTeX
@misc{eprint-2008-18168,
title={Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift},
booktitle={IACR Eprint archive},
keywords={public-key cryptography /},
url={http://eprint.iacr.org/2008/390},
note={ ajmeneze@uwaterloo.ca 14155 received 11 Sep 2008, last revised 3 Oct 2008},
author={Ann Hibner Koblitz and Neal Koblitz and Alfred Menezes},
year=2008
}


text:
Dier, D., Kemppainen, J., Siljander, J. et al. On the parabolic Harnack inequality for non-local diffusion equations. Math. Z. 295, 1751–1769 (2020). https://doi.org/10.1007/s00209-019-02421-7

### On the parabolic Harnack inequality for non-local diffusion equations

Saved in:
Author: Dier, Dominik1; Kemppainen, Jukka2; Siljander, Juhana3;
Organizations: 1Institute of Applied Analysis, University of Ulm, 89069 Ulm, Germany
2Mathematics Division, P.O. Box 4500, 90014 University of Oulu, Finland
3Department of Mathematics and Statistics, University of Jyväskylä, P.O. Box 35, 40014 Jyväskylä, Finland
Format: article
Version: accepted version
Access: open
Online Access: PDF Full Text (PDF, 0.2 MB)
Language: English
Published: Springer Nature, 2020
Publish Date: 2020-11-11
Description:

# Abstract

We settle the open question concerning the Harnack inequality for globally positive solutions to non-local in time diffusion equations by constructing a counter-example for dimensions d ≥ β, where β ∈ (0,2] is the order of the equation with respect to the spatial variable. The equation can be non-local both in time and in space but for the counter-example it is important that the equation has a fractional time derivative. In this case, the fundamental solution is singular at the origin for all times t > 0 in dimensions d ≥ β. This underlines the markedly different behavior of time-fractional diffusion compared to the purely space-fractional case, where a local Harnack inequality is known. The key observation is that the memory strongly affects the estimates. In particular, if the initial data $$\mathit{u}_0 \in \mathit{L}_{loc}^{q}$$ for q larger than the critical value $$\frac{d}{\beta}$$ of the elliptic operator (−Δ)β/2, a non-local version of the Harnack inequality is still valid as we show. We also observe the critical dimension phenomenon already known from other contexts: the diffusion behavior is substantially different in higher dimensions than d = 1 provided β > 1, since we prove that the local Harnack inequality holds if d < β.

see all

Series: Mathematische Zeitschrift
ISSN: 0025-5874
ISSN-E: 1432-1823
ISSN-L: 0025-5874
Volume: 295
Pages: 1751 - 1769
DOI: 10.1007/s00209-019-02421-7


text:
## Thursday, April 2, 2009

### Lecture 21

Today we saw the completion of Sudan-Trevisan-Vadhan's proof of the Impagliazzo-Wigderson Theorem: if there is a positive $\epsilon > 0$ such that $E$ contains a language not in $SIZE(2^{\epsilon n})$, then $P = BPP$. This included Sudan's algorithm for list-decoding Reed-Solomon codes.

#### Post a Comment

Note: Only a member of this blog may post a comment.


text:
April 3, 2020

# Paper Group ANR 57

Automating Representation Discovery with MAP-Elites. TIME: A Transparent, Interpretable, Model-Adaptive and Explainable Neural Network for Dynamic Physical Processes. Accelerating Psychometric Screening Tests With Bayesian Active Differential Selection. Logistic Regression Regret: What’s the Catch?. Task-adaptive Asymmetric Deep Cross-modal Hashing …

#### Automating Representation Discovery with MAP-Elites

Title Automating Representation Discovery with MAP-Elites
Authors Adam Gaier, Alexander Asteroth, Jean-Baptiste Mouret
Abstract The way solutions are represented, or encoded, is usually the result of domain knowledge and experience. In this work, we combine MAP-Elites with Variational Autoencoders to learn a Data-Driven Encoding (DDE) that captures the essence of the highest-performing solutions while still able to encode a wide array of solutions. Our approach learns this data-driven encoding during optimization by balancing between exploiting the DDE to generalize the knowledge contained in the current archive of elites and exploring new representations that are not yet captured by the DDE. Learning representation during optimization allows the algorithm to solve high-dimensional problems, and provides a low-dimensional representation which can be then be re-used. We evaluate the DDE approach by evolving solutions for inverse kinematics of a planar arm (200 joint angles) and for gaits of a 6-legged robot in action space (a sequence of 60 positions for each of the 12 joints). We show that the DDE approach not only accelerates and improves optimization, but produces a powerful encoding that captures a bias for high performance while expressing a variety of solutions.
Published 2020-03-09
URL https://arxiv.org/abs/2003.04389v1
PDF https://arxiv.org/pdf/2003.04389v1.pdf
PWC https://paperswithcode.com/paper/automating-representation-discovery-with-map
Repo
Framework

#### TIME: A Transparent, Interpretable, Model-Adaptive and Explainable Neural Network for Dynamic Physical Processes

Title TIME: A Transparent, Interpretable, Model-Adaptive and Explainable Neural Network for Dynamic Physical Processes
Authors Gurpreet Singh, Soumyajit Gupta, Matt Lease, Clint N. Dawson
Abstract Partial Differential Equations are infinite dimensional encoded representations of physical processes. However, imbibing multiple observation data towards a coupled representation presents significant challenges. We present a fully convolutional architecture that captures the invariant structure of the domain to reconstruct the observable system. The proposed architecture is significantly low-weight compared to other networks for such problems. Our intent is to learn coupled dynamic processes interpreted as deviations from true kernels representing isolated processes for model-adaptivity. Experimental analysis shows that our architecture is robust and transparent in capturing process kernels and system anomalies. We also show that high weights representation is not only redundant but also impacts network interpretability. Our design is guided by domain knowledge, with isolated process representations serving as ground truths for verification. These allow us to identify redundant kernels and their manifestations in activation maps to guide better designs that are both interpretable and explainable unlike traditional deep-nets.
Published 2020-03-05
URL https://arxiv.org/abs/2003.02426v2
PDF https://arxiv.org/pdf/2003.02426v2.pdf
PWC https://paperswithcode.com/paper/time-a-transparent-interpretable-model
Repo
Framework

#### Accelerating Psychometric Screening Tests With Bayesian Active Differential Selection

Title Accelerating Psychometric Screening Tests With Bayesian Active Differential Selection
Authors Trevor J. Larsen, Gustavo Malkomes, Dennis L. Barbour
Abstract Classical methods for psychometric function estimation either require excessive measurements or produce only a low-resolution approximation of the target psychometric function. In this paper, we propose a novel solution for rapid screening for a change in the psychometric function estimation of a given patient. We use Bayesian active model selection to perform an automated pure-tone audiogram test with the goal of quickly finding if the current audiogram will be different from a previous audiogram. We validate our approach using audiometric data from the National Institute for Occupational Safety and Health NIOSH. Initial results show that with a few tones we can detect if the patient’s audiometric function has changed between the two test sessions with high confidence.
Published 2020-02-04
URL https://arxiv.org/abs/2002.01547v1
PDF https://arxiv.org/pdf/2002.01547v1.pdf
PWC https://paperswithcode.com/paper/accelerating-psychometric-screening-tests
Repo
Framework

#### Logistic Regression Regret: What’s the Catch?

Title Logistic Regression Regret: What’s the Catch?
Authors Gil I. Shamir
Abstract We address the problem of the achievable regret rates with online logistic regression. We derive lower bounds with logarithmic regret under $L_1$, $L_2$, and $L_\infty$ constraints on the parameter values. The bounds are dominated by $d/2 \log T$, where $T$ is the horizon and $d$ is the dimensionality of the parameter space. We show their achievability for $d=o(T^{1/3})$ in all these cases with Bayesian methods, that achieve them up to a $d/2 \log d$ term. Interesting different behaviors are shown for larger dimensionality. Specifically, on the negative side, if $d = \Omega(\sqrt{T})$, any algorithm is guaranteed regret of $\Omega(d \log T)$ (greater than $\Omega(\sqrt{T})$) under $L_\infty$ constraints on the parameters (and the example features). On the positive side, under $L_1$ constraints on the parameters, there exist algorithms that can achieve regret that is sub-linear in $d$ for the asymptotically larger values of $d$. For $L_2$ constraints, it is shown that for large enough $d$, the regret remains linear in $d$ but no longer logarithmic in $T$. Adapting the redundancy-capacity theorem from information theory, we demonstrate a principled methodology based on grids of parameters to derive lower bounds. Grids are also utilized to derive some upper bounds. Our results strengthen results by Kakade and Ng (2005) and Foster et al. (2018) for upper bounds for this problem, introduce novel lower bounds, and adapt a methodology that can be used to obtain such bounds for other related problems. They also give a novel characterization of the asymptotic behavior when the dimension of the parameter space is allowed to grow with $T$. They additionally establish connections to the information theory literature, demonstrating that the actual regret for logistic regression depends on the richness of the parameter class, where even within this problem, richer classes lead to greater regret.
Published 2020-02-07
URL https://arxiv.org/abs/2002.02950v2
PDF https://arxiv.org/pdf/2002.02950v2.pdf
PWC https://paperswithcode.com/paper/logistic-regression-regret-whats-the-catch
Repo
Framework

Authors Tong Wang, Lei Zhu, Zhiyong Cheng, Jingjing Li, Huaxiang Zhang
Published 2020-04-01
URL https://arxiv.org/abs/2004.00197v1
PDF https://arxiv.org/pdf/2004.00197v1.pdf
Repo
Framework

#### The Sample Complexity of Meta Sparse Regression

Title The Sample Complexity of Meta Sparse Regression
Authors Zhanyu Wang, Jean Honorio
Published 2020-02-22
URL https://arxiv.org/abs/2002.09587v1
PDF https://arxiv.org/pdf/2002.09587v1.pdf
PWC https://paperswithcode.com/paper/the-sample-complexity-of-meta-sparse
Repo
Framework

#### The Future of Digital Health with Federated Learning

Title The Future of Digital Health with Federated Learning
Authors Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger Roth, Shadi Albarqouni, Spyridon Bakas, Mathieu N. Galtier, Bennett Landman, Klaus Maier-Hein, Sebastien Ourselin, Micah Sheller, Ronald M. Summers, Andrew Trask, Daguang Xu, Maximilian Baust, M. Jorge Cardoso
Abstract Data-driven Machine Learning has emerged as a promising approach for building accurate and robust statistical models from medical data, which is collected in huge volumes by modern healthcare systems. Existing medical data is not fully exploited by ML primarily because it sits in data silos and privacy concerns restrict access to this data. However, without access to sufficient data, ML will be prevented from reaching its full potential and, ultimately, from making the transition from research to clinical practice. This paper considers key factors contributing to this issue, explores how Federated Learning (FL) may provide a solution for the future of digital health and highlights the challenges and considerations that need to be addressed.
Published 2020-03-18
URL https://arxiv.org/abs/2003.08119v1
PDF https://arxiv.org/pdf/2003.08119v1.pdf
PWC https://paperswithcode.com/paper/the-future-of-digital-health-with-federated
Repo
Framework

#### Crime Prediction Using Spatio-Temporal Data

Title Crime Prediction Using Spatio-Temporal Data
Authors Sohrab Hossain, Ahmed Abtahee, Imran Kashem, Mohammed Moshiul Hoque, Iqbal H. Sarker
Abstract A crime is a punishable offence that is harmful for an individual and his society. It is obvious to comprehend the patterns of criminal activity to prevent them. Research can help society to prevent and solve crime activates. Study shows that only 10 percent offenders commits 50 percent of the total offences. The enforcement team can respond faster if they have early information and pre-knowledge about crime activities of the different points of a city. In this paper, supervised learning technique is used to predict crimes with better accuracy. The proposed system predicts crimes by analyzing data-set that contains records of previously committed crimes and their patterns. The system stands on two main algorithms - i) decision tree, and ii) k-nearest neighbor. Random Forest algorithm and Adaboost are used to increase the accuracy of the prediction. Finally, oversampling is used for better accuracy. The proposed system is feed with a criminal-activity data set of twelve years of San Francisco city.
Published 2020-03-11
URL https://arxiv.org/abs/2003.09322v1
PDF https://arxiv.org/pdf/2003.09322v1.pdf
PWC https://paperswithcode.com/paper/crime-prediction-using-spatio-temporal-data
Repo
Framework

#### Modeling of Spatio-Temporal Hawkes Processes with Randomized Kernels

Title Modeling of Spatio-Temporal Hawkes Processes with Randomized Kernels
Authors Fatih Ilhan, Suleyman Serdar Kozat
Abstract We investigate spatio-temporal event analysis using point processes. Inferring the dynamics of event sequences spatiotemporally has many practical applications including crime prediction, social media analysis, and traffic forecasting. In particular, we focus on spatio-temporal Hawkes processes that are commonly used due to their capability to capture excitations between event occurrences. We introduce a novel inference framework based on randomized transformations and gradient descent to learn the process. We replace the spatial kernel calculations by randomized Fourier feature-based transformations. The introduced randomization by this representation provides flexibility while modeling the spatial excitation between events. Moreover, the system described by the process is expressed within closed-form in terms of scalable matrix operations. During the optimization, we use maximum likelihood estimation approach and gradient descent while properly handling positivity and orthonormality constraints. The experiment results show the improvements achieved by the introduced method in terms of fitting capability in synthetic and real datasets with respect to the conventional inference methods in the spatio-temporal Hawkes process literature. We also analyze the triggering interactions between event types and how their dynamics change in space and time through the interpretation of learned parameters.
Published 2020-03-07
URL https://arxiv.org/abs/2003.03671v1
PDF https://arxiv.org/pdf/2003.03671v1.pdf
PWC https://paperswithcode.com/paper/modeling-of-spatio-temporal-hawkes-processes
Repo
Framework

#### A Comparative Study on Crime in Denver City Based on Machine Learning and Data Mining

Title A Comparative Study on Crime in Denver City Based on Machine Learning and Data Mining
Authors Md. Aminur Rab Ratul
Abstract To ensure the security of the general mass, crime prevention is one of the most higher priorities for any government. An accurate crime prediction model can help the government, law enforcement to prevent violence, detect the criminals in advance, allocate the government resources, and recognize problems causing crimes. To construct any future-oriented tools, examine and understand the crime patterns in the earliest possible time is essential. In this paper, I analyzed a real-world crime and accident dataset of Denver county, USA, from January 2014 to May 2019, which containing 478,578 incidents. This project aims to predict and highlights the trends of occurrence that will, in return, support the law enforcement agencies and government to discover the preventive measures from the prediction rates. At first, I apply several statistical analysis supported by several data visualization approaches. Then, I implement various classification algorithms such as Random Forest, Decision Tree, AdaBoost Classifier, Extra Tree Classifier, Linear Discriminant Analysis, K-Neighbors Classifiers, and 4 Ensemble Models to classify 15 different classes of crimes. The outcomes are captured using two popular test methods: train-test split, and k-fold cross-validation. Moreover, to evaluate the performance flawlessly, I also utilize precision, recall, F1-score, Mean Squared Error (MSE), ROC curve, and paired-T-test. Except for the AdaBoost classifier, most of the algorithms exhibit satisfactory accuracy. Random Forest, Decision Tree, Ensemble Model 1, 3, and 4 even produce me more than 90% accuracy. Among all the approaches, Ensemble Model 4 presented superior results for every evaluation basis. This study could be useful to raise the awareness of peoples regarding the occurrence locations and to assist security agencies to predict future outbreaks of violence in a specific area within a particular time.
Published 2020-01-09
URL https://arxiv.org/abs/2001.02802v1
PDF https://arxiv.org/pdf/2001.02802v1.pdf
PWC https://paperswithcode.com/paper/a-comparative-study-on-crime-in-denver-city
Repo
Framework

#### EEG-based Brain-Computer Interfaces (BCIs): A Survey of Recent Studies on Signal Sensing Technologies and Computational Intelligence Approaches and their Applications

Title EEG-based Brain-Computer Interfaces (BCIs): A Survey of Recent Studies on Signal Sensing Technologies and Computational Intelligence Approaches and their Applications
Authors Xiaotong Gu, Zehong Cao, Alireza Jolfaei, Peng Xu, Dongrui Wu, Tzyy-Ping Jung, Chin-Teng Lin
Abstract Brain-Computer Interface (BCI) is a powerful communication tool between users and systems, which enhances the capability of the human brain in communicating and interacting with the environment directly. Advances in neuroscience and computer science in the past decades have led to exciting developments in BCI, thereby making BCI a top interdisciplinary research area in computational neuroscience and intelligence. Recent technological advances such as wearable sensing devices, real-time data streaming, machine learning, and deep learning approaches have increased interest in electroencephalographic (EEG) based BCI for translational and healthcare applications. Many people benefit from EEG-based BCIs, which facilitate continuous monitoring of fluctuations in cognitive states under monotonous tasks in the workplace or at home. In this study, we survey the recent literature of EEG signal sensing technologies and computational intelligence approaches in BCI applications, compensated for the gaps in the systematic summary of the past five years (2015-2019). In specific, we first review the current status of BCI and its significant obstacles. Then, we present advanced signal sensing and enhancement technologies to collect and clean EEG signals, respectively. Furthermore, we demonstrate state-of-art computational intelligence techniques, including interpretable fuzzy models, transfer learning, deep learning, and combinations, to monitor, maintain, or track human cognitive states and operating performance in prevalent applications. Finally, we deliver a couple of innovative BCI-inspired healthcare applications and discuss some future research directions in EEG-based BCIs.
Published 2020-01-28
URL https://arxiv.org/abs/2001.11337v1
PDF https://arxiv.org/pdf/2001.11337v1.pdf
PWC https://paperswithcode.com/paper/eeg-based-brain-computer-interfaces-bcis-a
Repo
Framework

#### Spatiotemporal-Aware Augmented Reality: Redefining HCI in Image-Guided Therapy

Title Spatiotemporal-Aware Augmented Reality: Redefining HCI in Image-Guided Therapy
Authors Javad Fotouhi, Arian Mehrfard, Tianyu Song, Alex Johnson, Greg Osgood, Mathias Unberath, Mehran Armand, Nassir Navab
Abstract Suboptimal interaction with patient data and challenges in mastering 3D anatomy based on ill-posed 2D interventional images are essential concerns in image-guided therapies. Augmented reality (AR) has been introduced in the operating rooms in the last decade; however, in image-guided interventions, it has often only been considered as a visualization device improving traditional workflows. As a consequence, the technology is gaining minimum maturity that it requires to redefine new procedures, user interfaces, and interactions. The main contribution of this paper is to reveal how exemplary workflows are redefined by taking full advantage of head-mounted displays when entirely co-registered with the imaging system at all times. The proposed AR landscape is enabled by co-localizing the users and the imaging devices via the operating room environment and exploiting all involved frustums to move spatial information between different bodies. The awareness of the system from the geometric and physical characteristics of X-ray imaging allows the redefinition of different human-machine interfaces. We demonstrate that this AR paradigm is generic, and can benefit a wide variety of procedures. Our system achieved an error of $4.76\pm2.91$ mm for placing K-wire in a fracture management procedure, and yielded errors of $1.57\pm1.16^\circ$ and $1.46\pm1.00^\circ$ in the abduction and anteversion angles, respectively, for total hip arthroplasty. We hope that our holistic approach towards improving the interface of surgery not only augments the surgeon’s capabilities but also augments the surgical team’s experience in carrying out an effective intervention with reduced complications and provide novel approaches of documenting procedures for training purposes.
Published 2020-03-04
URL https://arxiv.org/abs/2003.02260v1
PDF https://arxiv.org/pdf/2003.02260v1.pdf
PWC https://paperswithcode.com/paper/spatiotemporal-aware-augmented-reality
Repo
Framework

#### Differentially Private Mean Embeddings with Random Features (DP-MERF) for Simple & Practical Synthetic Data Generation

Title Differentially Private Mean Embeddings with Random Features (DP-MERF) for Simple & Practical Synthetic Data Generation
Authors Frederik Harder, Kamil Adamczewski, Mijung Park
Abstract We present a differentially private data generation paradigm using random feature representations of kernel mean embeddings when comparing the distribution of true data with that of synthetic data. We exploit the random feature representations for two important benefits. First, we require a very low privacy cost for training deep generative models. This is because unlike kernel-based distance metrics that require computing the kernel matrix on all pairs of true and synthetic data points, we can detach the data-dependent term from the term solely dependent on synthetic data. Hence, we need to perturb the data-dependent term once-for-all and then use it until the end of the generator training. Second, we can obtain an analytic sensitivity of the kernel mean embedding as the random features are norm bounded by construction. This removes the necessity of hyperparameter search for a clipping norm to handle the unknown sensitivity of an encoder network when dealing with high-dimensional data. We provide several variants of our algorithm, differentially private mean embeddings with random features (DP-MERF) to generate (a) heterogeneous tabular data, (b) input features and corresponding labels jointly; and (c) high-dimensional data. Our algorithm achieves better privacy-utility trade-offs than existing methods tested on several datasets.
Published 2020-02-26
URL https://arxiv.org/abs/2002.11603v2
PDF https://arxiv.org/pdf/2002.11603v2.pdf
PWC https://paperswithcode.com/paper/differentially-private-mean-embeddings-with
Repo
Framework

#### Robust Learning from Discriminative Feature Feedback

Title Robust Learning from Discriminative Feature Feedback
Authors Sanjoy Dasgupta, Sivan Sabato
Abstract Recent work introduced the model of learning from discriminative feature feedback, in which a human annotator not only provides labels of instances, but also identifies discriminative features that highlight important differences between pairs of instances. It was shown that such feedback can be conducive to learning, and makes it possible to efficiently learn some concept classes that would otherwise be intractable. However, these results all relied upon perfect annotator feedback. In this paper, we introduce a more realistic, robust version of the framework, in which the annotator is allowed to make mistakes. We show how such errors can be handled algorithmically, in both an adversarial and a stochastic setting. In particular, we derive regret bounds in both settings that, as in the case of a perfect annotator, are independent of the number of features. We show that this result cannot be obtained by a naive reduction from the robust setting to the non-robust setting.
Published 2020-03-09
URL https://arxiv.org/abs/2003.03946v1
PDF https://arxiv.org/pdf/2003.03946v1.pdf
PWC https://paperswithcode.com/paper/robust-learning-from-discriminative-feature
Repo
Framework

#### Automatic Extraction of Bengali Root Verbs using Paninian Grammar

Title Automatic Extraction of Bengali Root Verbs using Paninian Grammar
Authors Arijit Das, Tapas Halder, Diganta Saha
Abstract In this research work, we have proposed an algorithm based on supervised learning methodology to extract the root forms of the Bengali verbs using the grammatical rules proposed by Panini [1] in Ashtadhyayi. This methodology can be applied for the languages which are derived from Sanskrit. The proposed system has been developed based on tense, person and morphological inflections of the verbs to find their root forms. The work has been executed in two phases: first, the surface level forms or inflected forms of the verbs have been classified into a certain number of groups of similar tense and person. For this task, a standard pattern, available in Bengali language has been used. Next, a set of rules have been applied to extract the root form from the surface level forms of a verb. The system has been tested on 10000 verbs collected from the Bengali text corpus developed in the TDIL project of the Govt. of India. The accuracy of the output has been achieved 98% which is verified by a linguistic expert. Root verb identification is a key step in semantic searching, multi-sentence search query processing, understanding the meaning of a language, disambiguation of word sense, classification of the sentences etc.